假设我有一个V结点和E边的无向图。如果我用邻接表表示图，则如果我有x和y之间的边的表示，我还必须有y和x之间的边的表示。邻接表。
我知道有向图的DFS具有V + E复杂度。对于无向图，它不具有v + 2 * e复杂度，因为您访问了每个边2次吗？想。谢谢你，
最佳答案
复杂度通常表示为O(| V | + | E |)，并且不受因子2的影响。
但是因子2实际上在那里。一个无向边仅表现为第2行有向边。例如。该算法(对于连接的无向图)是
visit(v) {
mark(v)
for each unmarked w adjacent to v, visit(w)
}
for循环将考虑每个入射到每个顶点的边一次。由于每个无向边都入射到2个顶点，因此很明显它将被视为两次!
请注意，无向DFS不必担心从所有源重新启动。您可以选择任何顶点。