Discussion on Graphs

Additional notes

The running times of the depth-first-search and breadth-first-search algorithms are somewhat overstated by the following theorems we explained before:

1. When given as input a Graph, g, that is implemented using the AdjacencyLists data structure, the bfs(g, r) algorithm runs in $O(n + m)$ time.
2. When given as input a Graph, g, that is implemented using the AdjacencyLists data structure, the dfs(g,r) and dfs2(g,r) algorithms each run in $O(n + m)$

...