关于无向图复杂性的DFS

Question

假设我有一个带有V节点和E边的无向图.如果我用相邻列表表示图,如果我有一个x和y之间的边的表示,我还必须表示y和x之间的边.邻接清单.

我知道有向图的DFS具有V + E复杂性.对于无向图,它没有v + 2*e复杂度,因为你访问每个边2次？抱歉,如果这是一个noobish问题..我真的想了解这个想.谢谢,

Answer 1

复杂度通常表示为 O(|V| + |E|)，并且不受 2 的影响。

但2的因数实际上是存在的。一条无向边的行为与第 2 行有向边相同。例如，算法（对于连通无向图）是

visit(v) {
  mark(v)
  for each unmarked w adjacent to v, visit(w)
}

for 循环将考虑与每个顶点相关的每条边一次。由于每条无向边都与 2 个顶点相关，因此显然会被考虑两次！

请注意，无向 DFS 不必担心从所有源重新启动。您可以选择任何顶点。