DFS on undirected graph complexity

6
votes

Let's say I have an undirected graph with V nodes and E edges.If I represent the graph with adjacency lists,if I have a representation of an edge between x and y,I must also have a representation of the edge between y and x in the adjacency list.

I know that DFS for directed graphs has V+E complexity.For undirected graphs doesn't it have v+2*e complexity ,because you visit each edge 2 times ?Sorry if it's a noobish question..I really want to understand this think.Thank you,

1
graphtime-complexitydepth-first-search
See answer here stackoverflow.com/questions/11468621/… - superk
If the graph is acyclic then the cost is Theta(|V|). It can be otherwise stated that detecting a cycle in undirected graph takes O(|V|) time. - shuva

1 Answers

4
votes

The complexity is normally expressed O(|V| + |E|) and this isn't affected by the factor of 2.

But the factor of 2 is actually there. One undirected edge behaves just line 2 directed edges. E.g. the algorithm (for a connected undirected graph) is

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

The for loop will consider each edge incident to each vertex once. Since each undirected edge is incident to 2 vertices, it will clearly be considered twice!

Note the undirected DFS doesn't have to worry about restarting from all the sources. You can pick any vertex.