Graph Traversal

As for Trees, we can traverse a Graph by using DFS or BFS.

The complexity of the two algorithms is $O(|V|+|E|)$ for both time and space, where:

• $|V|$¹ represents the number of the Vertices/Nodes.
• $|E|$¹ represents the number of the Edges.

In fact, we need $|E|$ time to build the Adjacency List and $|V|$ time to push and pop elements to and from the stack, respectively.

Regarding the space, we need to store $|E|$ edges in the dictionary and $|V|$ Vertices/Nodes in the set.

1. $|S|$ means the cardinality of the set $S$, which is the number of elements. ↩ ↩2