I am working with an algorithm to compute the transpose of a directed graph. Here is a rough overview of the algorithm: For each vertex in the graph, traverse each edge and add an edge from the neighbor to the parent node. The adding of an edge takes constant time, $O(1)$. And I figured, if I am traversing each edge, then the asymptotic run time should be $O(|E|)$. However, the run time of this algorithm is $O(|V| + |E|)$. The only way I can make sense of this is: once it reaches the final level of the tree (the roots), even though the nodes don't have any edges, the for loop will still iterate through those nodes. However, if I am taking this into account, then shouldn't it be $O(|V|)$. Why are we taking both $|V|$ and $|E|$ into account? Can someone can offer some insight to this?
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ Do you even need an algorithm to do this? In many contexts, you can just have a Boolean field for "The edges go the other way, now." Now, transposing the graph is $O(1)$ (flip the Boolean), and any algorithms that use your graph data structure just need to check the Boolean and behave appropriately. $\endgroup$– David RicherbyCommented Oct 19, 2016 at 18:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
It all depends on how exactly you store the graph. For example:
- If you store the graph as an adjacency matrix, the complexity is $\Theta(|V|^2)$.
- If you store the graph as a linked list of edges per vertex (i.e., adjacency lists), then the complexity is $\Theta(|V|+|E|)$.
- If you store the graph as a linked list of all edges (and don't store the vertices explicitly), then the complexity is $\Theta(|E|)$.
The representations usually used are the first two. I have never heard of the third being used. In most cases, the number of edges exceeds the number of vertices, and so there would be the third method would have no advantage over the second one, but it would have many disadvantages.
answered Oct 19, 2016 at 18:09
-
$\begingroup$ I encountered the problem of finding transpose of graph G in CLRS book. There graph is represented by adjacency list.They say that time complexity is $O(V+E)$. I know that $Θ(V+E)->O(V+E)$.But why are they specifically using $O$ while they have used $Θ$ while dealing with DFS which actually is so.While analyzing algo of transpose I found it as $Θ$. for each vertex u in G we scan the adjacency list of it and for each of the adjacent vertex v of u, u is added to the front of adjacency list of v in transpose(G).By aggregate analysis i find that it $Θ$ as each and every edge in G is explored $\endgroup$ Commented Apr 8, 2020 at 9:18