algorithm - 如何访问无向图中的顶点

Question

从任意位置访问无向图的所有顶点的正确算法是什么？例如，给定以下具有 7 个顶点的图，从 #6 开始:

有很多可能的顺序:67645321,676421235,6453212467,...

如何用最短路径(第一个)迭代顶点？谢谢。

Answer 1

跟进我上面的评论，

1-2-3
  | |
  4-5
  |
  6-7

按节点值排序，值小的排在前面，结果:

6-+-4-+-2-+-1
  `-7 `-5 `-3

遍历树:

6-4-2-1-2-3-2-4-5-4-6-7

可以做一些更多的优化，例如对于每个节点，保持每个“ child ”的“深度”或权重，首先横穿浅 child /轻 child 。

6-+-(5)-4-+-(3)-2-+-(1)-1
  `-(1)-7 `-(1)-5 `-(1)-3

因此我们横向如下:

6-7-6-4-5-4-2-1-2-3

可能还有更多方法可以优化，祝你好运!