Mastering Algorithms With C - Kyle Loudon [114]
Connectivity is another important concept in graphs. An undirected graph is connected if every vertex is reachable from each other by following some path. If this is true in a directed graph, we say the graph is strongly connected . Although an undirected graph may not be connected, it still may contain certain sections that are connected, called connected components . If only parts of a directed graph are strongly connected, the parts are strongly connected components (see Figure 11.3).
Certain vertices have special significance in keeping a graph or connected component connected. If removing a vertex disconnects a graph or component, the vertex is an articulation point . For example, in Figure 11.4, vertices 4 and 5 are articulation points because if either of them is removed, the graph becomes disconnected. Upon removing these vertices, the graph has two connected components, {1, 2, 3} and {6, 7, 8}. Any edge whose removal disconnects a graph is called a bridge . A connected graph with no articulation points is biconnected . Although a graph may not be biconnected, it still may contain biconnected components .
Figure 11.2. Two graphs: (a) a directed graph containing the cycle {1, 2, 4, 1}, and (b) a directed acyclic graph, or dag
Figure 11.3. A directed graph with two strongly connected components, {1, 2, 3} and {4, 5, 6}
Figure 11.4. An undirected graph with articulation points 4 and 5, and the bridge (4, 5)
The most common way to represent a graph in a computer is using an adjacency-list representation. This consists of a linked list of adjacency-list structures. Each structure in the list contains two members: a vertex and a list of vertices adjacent to the vertex (see Figure 11.5).
In a graph G = (V, E ), if two vertices u and v in V form an edge (u, v) in E, vertex v is included in the adjacency list of vertex u. Thus, in a directed graph, the total number of vertices in all adjacency lists is the same as the total number of edges. In an undirected graph, since an edge (u, v) implies an edge (v, u), vertex v is included in the adjacency list of vertex u, and vertex u is included in the adjacency list of vertex v. Thus, the total number of vertices in all adjacency lists in this case is twice the total number of edges.
Figure 11.5. An adjacency-list representation of the directed graph from Figure 11.3
Typically, adjacency lists are used for graphs that are sparse, that is, graphs in which the number of edges is less than the number of vertices squared. Sparse graphs are common. However, if a graph is dense , we may choose to represent it using an adjacency-matrix representation (see the related topics at the end of the chapter). Adjacency-matrix representations require O (VE ) space.
Search Methods
Searching a graph means visiting its vertices one at a time in a specific order. There are two important search methods from which many important graph algorithms are derived: breadth-first search and depth-first search.
Breadth-first search
Breadth-first search (see Figure 11.6) explores a graph by visiting all vertices adjacent to a vertex before exploring the graph further. This search is useful in a number of applications, including finding minimum spanning trees and shortest paths (see Chapter 16 and the first example in this chapter).
Figure 11.6. Breadth-first search starting at vertex 1; vertex 5 is unreachable from 1
To begin, we select a start vertex and color it gray. We color all other vertices in the graph white. The start vertex is also placed alone in a queue. The algorithm then proceeds as follows: for each vertex in the queue (initially only the start vertex), we peek at the vertex at the front of the queue and explore each vertex adjacent to it. As each adjacent vertex is explored,