访问无向图中的边、顶点

Question

问题:您有一个无向图G = (V, E) (V =顶点，E=边)，并且您必须访问每个顶点并在两个方向上传递每个边。

我所知道的图形算法只有DFS、BFS和一些MST (Kruskal等)。我和我的朋友正在讨论这个问题，如果它是有向的，我会简单地DFS，然后DFS转置，但不幸的是图是无向的。我的朋友建议我们执行MST，并对MST进行DFS，然后通过迭代那些不在MST中的边来找到剩余的边。我有点明白他的意思，但我不确定这是不是一个好的方法？意见？另外，如果边是无方向的，我如何在两个方向上通过它？

Answer 1

图是有向的还是无向的并不重要。您只需将每条无向边替换为两条有向边，并对有向图执行任何算法。DFS和BFS都将遍历整个顶点和边。

我想你要找的东西叫做Graph Traversal。BFS和DFS是两种图遍历算法，它们不需要对图进行定向。另一方面，MST不是一种图遍历算法。