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

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 不是图遍历算法。