graph - 无向图复杂度上的 DFS

Question

假设我有一个带有 V 节点和 E 边的无向图。如果我用邻接表表示图，如果我有 x 和 y 之间的边的表示，我还必须有 y 和 x 之间的边的表示邻接表。

我知道有向图的 DFS 具有 V+E 复杂度。对于无向图，它没有 v+2*e 复杂度，因为您访问每条边 2 次？对不起，如果这是一个愚蠢的问题..我真的很想了解这一点想想。谢谢，

Answer 1

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

但实际上 2 的因素是存在的。一条无向边仅表现第 2 行有向边。例如，算法（对于连接的无向图）是

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

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

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