无向图复杂性的DFS

Question

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

我知道有向图的DFS具有VE复杂性。对于无向图，它没有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循环将考虑每一个边缘入射到每个顶点一次。由于每个无向边都与两个顶点相关，因此显然会考虑两次！

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