遍历一个扭曲的无向,未加权的图形:每个节点的最小访问量
Smi*_*ims 5 java algorithm graph-theory graph
我正在尝试编写将遍历未定向的未加权图形的代码.本质上,该方法将被传递一个节点(它知道它的所有邻居).然后,该方法必须通过从一个节点到另一个节点有效地构建图形模型,并收集节点相互链接的信息.最后,该方法将包含所有节点和连接它们的所有顶点的完整列表.
*问题的关键在于有效的词和我的意思.让我把注意力转向这个小图:
假设我从节点G开始.我可以访问C,B,F,D,H,J或E.我想最小化访问节点的次数,为了访问节点,我必须通过在前往该节点的途中的所有节点.
示例:假设我决定访问节点C.下一个要访问的节点可以是A,B,F,D,H,J或E.但是,要访问除A之外的任何节点,我必须通过G再次被认为效率低下.并且为了访问A,我将不得不再次访问G和C然后通过C然后G返回到图的其余部分.所以我决定访问A.这意味着我必须再次通过C才能到达G.因此,从逻辑的角度来看,最后访问C分支是有意义的.
但是,程序从节点G开始时,并不知道分支C导致死胡同.在我写这篇文章的时候,我认为这可能是不可能的,但我还是会问它:无论如何都要尽可能有效地遍历这个图表(正如我之前所定义的那样)只使用给定的信息(即程序只知道关于它访问过的节点和从那些节点发出的边缘？或者我应该使用变量Dijkstra的算法来确保我访问每个节点？
如果重要的话,这将全部用Java编写.
您是否想简单地遍历整个图（无论采用哪条路径），并对每个节点执行一些操作，或者您想计算从一个节点到任何其他节点的最短路径？（我可能不明白你的目标。）
在第一种情况下，坚持使用遍历算法，例如广度优先搜索。对于另一个，您可能需要使用相同权重的边（即 = 1）来考虑Dijkstra 。
当您只对一个起始节点感兴趣并且所有边都具有相同的权重时，您可以将 BFS 视为 Dijkstra 的一种特例。对于不同的成本，您可以使用统一成本搜索。