Menu
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,
332
We use an undirected graph with 5 vertices. We start from vertex 0, the DFS algorithm starts by putting it in the Visited list and putting all its adjacent vertices in the stack. Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes.
Complexity Of Depth-First Search Algorithm If the entire graph is traversed, the temporal complexity of DFS is O(V), where V is the number of vertices. If the graph data structure is represented as an adjacency list, the following rules apply: Each vertex keeps track of all of its neighboring edges.
DFS suffers from the same problem in undirected graphs: if your graph is not connected, then starting DFS with an initial vertex $v$ will only explore the connected component of $v$. In a similar fashion, if the graph is directed, then DFS will only explore the vertices reachable from $v$.
Space Complexity of DFS Space complexity is a measure of the amount of working storage an algorithm needs. That means how much memory, in the worst case, is needed at any point in the algorithm.
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.
98
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
