algorithm - 访问无向图中的边、顶点

Question

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

我所知道的图算法只有 DFS、BFS 和一些 MST(Kruskal 等)不幸的是，图是无向的。我的 friend 建议我们对 MST 执行 MST 和 DFS，然后通过迭代那些不在 MST 中的边来找到剩余的边。我有点明白他的意思，但我不确定这是一个好方法吗？意见？另外，如果一条边是无向的，我如何才能在两个方向上通过它？

Answer 1

图形是有向的还是无向的并不重要。您可以只用两个有向边替换每个无向边，并执行您对有向图的任何算法。 DFS和BFS都会遍历所有的顶点和边。

我想你要找的是 Graph Traversal . BFS 和 DFS 是两种图遍历算法，它们不需要图是有向的。另一方面，MST 不是图遍历算法。