Graphs:Searching a Graph

Searching a Graph

It is evident that for answering almost any nontrivial question about a given graph G we must examine every edge (and in the process every vertex) of G at least once. For example, before declaring a graph G to be disconnected we must have looked at every edge in G; for otherwise, it might happen that the one edge we had decided to ignore could have made the graph connected. The same can be said for questions of separability, planarity, and other properties [15, 16].

There are two natural ways of scanning or searching the edges of a graph as we move from vertex to vertex: (i) once at a vertex v we scan all edges incident on v and then move to an adjacent vertex w, then from w we scan all edges incident on w. This process is continued till all the edges reachable from v are scanned. This method of fanning out from a given vertex v and visiting all vertices reachable from v in order of their distances from v (i.e. first visit all vertices at a distance one from v, then all vertices at distances two from v, and so on) is referred to as the breadth-first search (BFS) of the graph. (ii) An opposite approach would be, instead of scanning every edge incident on vertex v, we move to an adjacent vertex w (a vertex not visited before) as soon as possible, leaving v with possibly unexplored edges for the time being. In other words, we trace a path through the graph going on to a new vertex whenever possible. This method of traversing the graph is called the depth-first search (DFS). Breadth-first and depth-first searches are fundamental methods of graph traversal that form the basis of many graph algorithms [7, 15, 16, 19]. The details of these two methods follow.

Depth-First Search

Depth-first search on an undirected graph G = (V, E) explores the graph as follows. When we are “visiting” a vertex v ∈ V , we follow one of the edges (v, w) incident on v. If the vertex w has been previously visited, we return to v and choose another edge. If the vertex w (at the other end of edge (v, w) from v) has not been previously visited, we visit it and apply the process recursively to w. If all the edges incident on v have been thus traversed, we go back along the edge (u, v) that had first led to the current vertex v and continue exploring the edges incident on u. We are finished when we try to back up from the vertex at which the exploration began.

Figure 4.8 illustrates how depth-first search examines an undirected graph G represented as an adjacency lists. We start with a vertex a. From a we traverse the first edge that we encounter, which is (a, b). Since b is a vertex never visited before, we stay at b and traverse the first untraversed edge encountered at b, which is (b, c). Now at vertex c, the first untraversed edge that we find is (c, a). We traverse (c, a) and find that a has been previously visited. So we return to c, marking the edge (c, a) in some way (as a dashed line in Figure 4.8(c)) to distinguish it from edges like (b, c), which lead to new vertices and shown as the thick lines. Back at vertex c, we look for another untraversed edge and traverse the first one that we encounter, which is (c, d). Once again, since d is a new vertex, we stay at d and look for an untraversed edge. And so on. The numbers next to the vertices in Figure 4.8(c) show the order in which they were visited; and the numbers next to the edges show the order in which they were traversed.

Depth-first search performed on a connected undirected graph G = (V, E), partitions the edge set into two types: (i) Those that led to new vertices during the search constitute the branches of a spanning tree of G and (ii) the remaining edges in E are called back edges because their traversal led to an already visited vertex from which we backed down to the current vertex.

A recursive depth-first search algorithm is given in Figure 4.9. Initially, every vertex x is marked unvisited by setting num[x] to 0. Note that in the algorithm shown in Figure 4.9, only the tree edges are kept track of. The time complexity of the depth-first search algorithm is O(m + n), provided the input is in the form of an adjacency matrix.

Breadth-First Search

In breadth-first search we start exploring from a specified vertex s and mark it “visited”. All other vertices of the given undirected graph G are marked as “unvisited” by setting num[] = 0. Then we visit all vertices adjacent to s (i.e., in the adjacency list of s). Next, we visit all unvisited vertices adjacent to the first vertex in the adjacency list of s. Unlike the depth-first search, in breadth-first search we explore (fan out) from vertices in order in which they themselves were visited. To implement this method of search, we maintain a queue (Q) of visited vertices. As we visit a new vertex for the first time, we place it in (i.e., at the back of) the queue. We take a vertex v from front of the queue and traverse all untraversed edges incident at v—adding to the list of tree edges those edges that lead to unvisited vertices from v ignoring the rest. Once a vertex v has been taken out of the queue, all the neighbors of v are visited and v is completely explored.

Thus, during the execution of a breadth-first search we have three types of vertices: (i) unvisited, those that have never been in the queue; (ii) completely explored, those that have been in the queue but are not now in the queue; and (iii) visited but not completely explored, i.e., those that are currently in the queue.

Since every vertex (reachable from the start vertex s) enters and exits the queue exactly once and every edge in the adjacency list of a vertex is traversed exactly once, the time complexity of the breadth-first search is O(n + m).

An algorithm for performing a breadth-first search on an undirected connected graph G from a specified vertex s is given in Figure 4.10. It produces a breadth-first tree in G rooted at vertex s. For example, the spanning tree produced by BFS conducted on the graph in Figure 4.8 starting at vertex a, is shown in Figure 4.11. The numbers next to the vertices show the order in which the vertices were visited during the BFS.