Graph Search
We often learn properties of a graph by systematically examining each of its vertices and each of its edges. Determining some simple graph propertiesâ€”for example, computing the degrees of all the verticesâ€”is easy if we just examine each edge (in any order whatever). Many other graph properties are related to paths, so a natural way to learn them is to move from vertex to vertex along the graph's edges. Nearly all the graphprocessing algorithms that we consider use this basic abstract model. In this chapter, we consider the fundamental graphsearch algorithms that we use to move through graphs, learning their structural properties as we go. Graph searching in this way is equivalent to exploring a maze. Specifically, passages in the maze correspond to edges in the graph, and points where passages intersect in the maze correspond to vertices in the graph. When a program changes the value of a variable from vertex v to vertex w because of an edge vw, we view it as equivalent to a person in a maze moving from point v to point w. We begin this chapter by examining a systematic exploration of a maze. By correspondence with this process, we see precisely how the basic graphsearch algorithms proceed through every edge and every vertex in a graph. In particular, the recursive depthfirst search (DFS) algorithm corresponds precisely to the particular mazeexploration strategy of . DFS is a classic and versatile algorithm that we use to solve connectivity and numerous other graphprocessing problems. The basic algorithm admits two simple implementations: one that is recursive, and another that uses an explicit stack. Replacing the stack with a FIFO queue leads to another classic algorithm, breadthfirst search (BFS), which we use to solve another class of graphprocessing problems related to shortest paths. The main topics of this chapter are DFS, BFS, their related algorithms, and their app to graph processing. We briefly considered DFS and BFS in Chapter 5; we treat them from first principles here, in the context of searchbased graphprocessing classes, and use them to demonstrate relationships among various graph algorithms. In particular, we consider a general approach to searching graphs that encompasses a number of classical graphprocessing algorithms, including both DFS and BFS. As illustrations of the app of these basic graphsearching methods to solve more complicated problems, we consider algorithms for finding connected components, biconnected components, spanning trees, and shortest paths, and for solving numerous other graphprocessing problems. These implementations exemplify the approach that we shall use to solve more difficult problems in s 19 through 22. We conclude the chapter by considering the basic issues involved in the analysis of graph algorithms, in the context of a case study comparing several different algorithms for finding the number of connected components in a graph.
