关于无向图复杂性的DFS

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

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

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

但实际上是2的因素.一个无向边缘仅表现为线2的有向边.例如.算法(对于连通的无向图)是

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

for循环将考虑每个顶点入射到每个顶点一次.由于每个无向边缘都入射到2个顶点,因此显然会被认为是两次!

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

相关文章
相关标签/搜索