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)$ time.

Define $n_r$ as the number of vertices, $i$, of $G$, for which there exists a path from $r$ to $i$. Define $m_r$ as the number of edges that have these vertices as their sources. Then the following theorem is a more precise statement of the running times of the breadth-first-search and depth-first-search algorithms.

Theorem: When given as input a Graph, g, that is implemented using the AdjacencyLists data structure, the bfs(g,r), dfs(g,r) and dfs2(g,r) algorithms each run in $O(n_r + m_r)$ time.

Breadth-first-search seems to have been discovered independently by MooreE. F. Moore. The shortest path through a maze. In Proceedings of the International Symposium on the Theory of Switching, pages 285–292, 1959. and LeeC. Y. Lee. An algorithm for path connection and its applications. IRE Transaction on Electronic Computers, EC-10(3):346–365, 1961. in the contexts of maze exploration and circuit routing, respectively.