6

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,

jfs
  • 399,953
  • 195
  • 994
  • 1,670
Emil Grigore
  • 929
  • 3
  • 13
  • 28
  • See answer here http://stackoverflow.com/questions/11468621/why-is-the-time-complexity-of-both-dfs-and-bfs-o-v-e – superk Oct 06 '13 at 23:18
  • 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. – KRoy May 10 '16 at 18:24

1 Answers1

4

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.

Gene
  • 46,253
  • 4
  • 58
  • 96