Prerequisite: Graph Concepts
Any aspiring computer scientist should make understanding graph search algorithms a priority because of their ubiquity and wide range of applications. There are two purposes for graph search. The first, and obvious, purpose is to locate a particular node. The second is to identify vertices reachable from a specified vertex. A vertex is reachable from another vertex if there is a path through the graph connecting the two vertices. While this may seem parochial, determining reachability is the cornerstone of more advanced analysis.
There are two primary types of graph search algorithms: breadth first and depth first. Both have the same goal - efficiently search a graph by only visiting each node once. As demonstrated below, they have the same basic structure with only slight deviations which make them uniquely suited for different purposes.
Unless otherwise specified, the graph search algorithms presented here work essentially the same for both directed and undirected graphs.
The asymptotic complexity of every algorithm presented in this section is $O(m + n)$. The actual run times are only slightly higher than the amount of time required to read the data. Because of this, graph search algorithms are considered free primitives.
Source Code
Relevant Files:
Click here for build and run instructions