# Runtime of algorithm to transpose a graph

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?

• 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. Oct 19 '16 at 18:28

• 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|)$.
• 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 Apr 8 '20 at 9:18