Transposed Graph

The transpose of $G$ (Notation $G^T$) is a graph $G$ with:

• Same Vertices as $G$
• Edge are reverses of $G$

Transpose Algorithm

Time complexity: $O(n+m)$

allocate array T of size n
for i in 0,...,n-1:
	node = A[i]
	while node != null:
		T[node.id] = create_node(i)
		node = node->next