Searching a Graph

Many problems can be described using graphs, where the solution to the problem requires that we search the graph, looking for nodes (or paths) with a certain property.

Two important graph exploration techniques are


Breadth-First Search Algorithm

  
  typedef int vertex;
  
  BFS (graph &G, vertex v)
  {
    vertex w,u;
    int mark[N];
    vnode *p;
    queue Q;
  
    for (w = 0; w < N; w++) mark[w] = 0;
    mark[v] = 1;
    Enqueue(Q,v);
    while (w = Front(Q)) {
       Dequeue(Q);
       p = G[w];
       while (p != NULL) { 
  	u = p->vertex;
  	if (! mark[u]) {
  	  mark[u] = 1;
  	  cout << u;
  	  Enqueue(Q,u);
  	}
  	p = p->next;
       }
    }
  } /* BFS */
  
  

Analysis of the Algorithm

Each vertex is placed in the queue once, so the outmoster while loop is executed at most N times.

Each edge is examined once in the innermost while loop, which is executed at most E times.

Assuming we maintain head and tail pointers for the queue, Enqueue, Dequeue, and Front are all O(1).

The algorithm requires O(N + E).

Since typically 0 < N << E << N^2, this is O(E).


Breadth-First Search and Die Hard

Use breadth-first search to solve the problem posed in Die Hard with a Vengeance -- Measure 4 gallons with two jugs that hold 5 and 3 gallons.

  Node     EmpB     EmpS     FillB    FillS    PourSB   PourBS
  
  (0,0)    (0,0)    (0,0)    (5,0)    (0,3)    (0,0)    (0,0)
  (0,1)    (0,1)    (0,0)    (5,1)    (0,3)    (1,0)    (0,1)
  (0,2)    (0,2)    (0,0)    (5,2)    (0,3)    (2,0)    (0,2)
  (0,3)    (0,3)    (0,0)    (5,3)    (0,3)    (3,0)    (0,3)
  (1,0)    (0,0)    (1,0)    (5,0)    (1,3)    (1,0)    (0,1)
  (1,1)    (0,1)    (1,0)    (5,1)    (1,3)    (2,0)    (0,2)
  (1,2)    (0,2)    (1,0)    (5,2)    (1,3)    (3,0)    (0,3)
  (1,3)    (0,3)    (1,0)    (5,3)    (1,3)    (4,0)    (1,3)
  (2,0)    (0,0)    (2,0)    (5,0)    (2,3)    (2,0)    (0,2) 
  (2,1)    (0,1)    (2,0)    (5,1)    (2,3)    (3,0)    (0,3)
  (2,2)    (0,2)    (2,0)    (5,2)    (2,3)    (4,0)    (1,3)
  (2,3)    (0,3)    (2,0)    (5,3)    (2,3)    (5,0)    (2,3)
  (3,0)    (0,0)    (3,0)    (5,0)    (3,3)    (3,0)    (0,3)
  (3,1)    (0,1)    (3,0)    (5,1)    (3,3)    (4,0)    (1,3)
  (3,2)    (0,2)    (3,0)    (5,2)    (3,3)    (5,0)    (2,3)
  (3,3)    (0,3)    (3,0)    (5,3)    (3,3)    (5,1)    (3,3)
  (4,0)    (0,0)    (4,0)    (5,0)    (4,3)    (4,0)    (1,3)
  (4,1)    (0,1)    (4,0)    (5,1)    (4,3)    (5,0)    (2,3)
  (4,2)    (0,2)    (4,0)    (5,2)    (4,3)    (5,1)    (3,3)
  (4,3)    (0,3)    (4,0)    (5,3)    (4,3)    (5,2)    (4,3)
  (5,0)    (0,0)    (5,0)    (5,0)    (5,3)    (5,0)    (2,3) 
  (5,1)    (0,1)    (5,0)    (5,1)    (5,3)    (5,1)    (3,3)
  (5,2)    (0,2)    (5,0)    (5,2)    (5,3)    (5,2)    (4,3) 
  (5,3)    (0,3)    (5,0)    (5,3)    (5,3)    (5,3)    (5,3)
  
  

Breadth-First Search in Die Hard

Here is the sequence in which nodes in the graph would be visited.

  Node     EmpB     EmpS     FillB    FillS    PourSB   PourBS
  
  (0,0)    (0,0)    (0,0)    (5,0)*   (0,3)*   (0,0)    (0,0)
  (5,0)    (0,0)    (5,0)    (5,0)    (5,3)*   (5,0)    (2,3)*
  (0,3)    (0,3)    (0,0)    (5,3)    (0,3)    (3,0)*   (0,3)
  (5,3)    (0,3)    (5,0)    (5,3)    (5,3)    (5,3)    (5,3)
  (2,3)    (0,3)    (2,0)*   (5,3)    (2,3)    (5,0)    (2,3)
  (3,0)    (0,0)    (3,0)    (5,0)    (3,3)*   (3,0)    (0,3)
  (2,0)    (0,0)    (2,0)    (5,0)    (2,3)    (2,0)    (0,2)*
  (3,3)    (0,3)    (3,0)    (5,3)    (3,3)    (5,1)*   (3,3)
  (0,2)    (0,2)    (0,0)    (5,2)*   (0,3)    (2,0)    (0,2)
  (5,1)    (0,1)*   (5,0)    (5,1)    (5,3)    (5,1)    (3,3)
  (5,2)    (0,2)    (5,0)    (5,2)    (5,3)    (5,2)    (4,3)*
  
  
  
  The queue contents over time would be:
  (0,0)
      (5,0)  (0,3)
          (5,3)  (2,3)
          (3,0)
              (2,0)
              (3,3)
                  (0,2)
                  (5,1)
                      (5,2)
                      (0,1)
                          (4,3)
  
  

Depth-First Search Algorithm

  
  typedef int vertex;
  int mark[N];
  struct vnode {int node; vnode *next;}
  struct vnode *G[N];
  
  DFS(vertex v) {
    struct vnode *p;
    vertex u;
    mark[v] = 1;
    p = G[v];
    while (p != NULL) { 
      u = p->node;
      if (! mark[u]) DFS(u);
      p = p->next;
    }
  } /* DFS */
  
  main()
  { vertex w;
    for (w = 0; w < N; w++) mark[w] = 0;
    for (w = 0; w < N; w++)
        if (! mark[w])
  	  DFS(w);
  } /* main */
  
  

Analysis of the Algorithm

The number of calls to DFS is O(N), since we never call DFS on a marked node, and we mark a node on entering DFS.

The total time spent traversing adjacency lists in the while loop of DFS is O(E).

The algorithm requires O(N + E).

Since typically 0 < N << E << N^2, this is O(E).


Depth-First Search in Die Hard


Here is the sequence in which nodes in the graph would be visited by DFS, starting at (0,0).

  
  (0,0)
  (5,0)  (5,3)
  (0,3)  (3,0)  (3,3)
  (5,1)
  (0,1)  (1,0)  (1,3)
  (4,0)
  
  

Depth-First Search Trees

Since we never visit a node twice, our exploration of a graph using DFS resembles a tree.

DFS(v) produces a depth-first search tree with node v at the root.

Each call to DFS in the main program above produces a different depth-first search tree.

In some graphs, it isn't possible to reach all nodes from a given start node. That is, a single call to DFS may not visit all nodes in the graph. This is why the main program given above calls DFS for every unmarked node in the graph.

The main program produces a depth-first search forest of the graph.


Using DFS for Postorder Numbering

  
  typedef int vertex;
  struct gnode {int mark; int postorder; vnode *header;}
  struct vnode {vertex node; vnode *next;}
  struct gnode G[N];
  int pocnt;
  
  DFS(vertex v) {
    struct vnode *p;
    vertex u;
    G[v].mark = 1;
    p = G[v].header;
    while (p != NULL) { 
      u = p->node;
      if (! G[u].mark) DFS(u);
      p = p->next;
    }
    G[v].postorder = pocnt++;
  } /* DFS */
  
  dfsForest()
  { vertex w;
    for (w = 0; w < N; w++) G[w].mark = 0;
    pocnt = 1;
    for (w = 0; w < N; w++)
        if (! G[w].mark)
  	  DFS(i);
  } /* dfsForest */
  
  

Testing for Cycles

We can use depth-first search to number graph nodes in postorder, and then use those numbers to test for cycles.

To find a cycle, we look for an edge (u,v) in the graph such that v is an ancestor of u in the search tree.

If there is an edge (u,v) in E, and the postorder number of u is less than or equal to the postorder number of v, the graph has a cycle.


Testing for Cycles: The Algorithm

  
  boolean Acyclic(int N, graph &G)
  { vertex u,v;
    dfsForest();
    for (u = 0; u < N; u++) {
        p = G[u].header;
        while (p != NULL) { 
           v = p->node;
           if (G[u].postorder <= G[v].postorder)
  	    return FALSE;
  	 p = p->next;
        }
    }
    return TRUE;
  } /* Acyclic */
  
  

Topological Sort

Topological sorting assigns a linear ordering to the vertices in a directed acyclic graph, such that if (i,j) is an edge, i appears before j in the ordering.

If we use postorder numbers to order nodes, then the reverse of this ordering is a topological sort.

  
  TopSort(vertex v) {
    /* Output vertices accessible from v
       in reverse topological order */
    struct vnode *p;
    vertex u;
    G[v].mark = 1;
    p = G[v].header;
    while (p != NULL) { 
      u = p->node;
      if (! G[u].mark) TopSort(u);
      p = p->next;
    }
    cout << v;
  } /* TopSort */
  
  

Topological Sort With a Stack

  
  stack S;
  
  TopSort(vertex v)
  { struct vnode *p;
    vertex u;
    G[v].mark = 1;
    p = G[v].header;
    while (p != NULL) { 
      u = p->node;
      if (! G[u].mark) TopSort(u);
      p = p->next;
    }
    Push(S,v);
  } /* TopSort */
  
  main()
  { vertex w;
    Initialize(S);
    for (w = 0; w < N; w++) mark[w] = 0;
    for (w = 0; w < N; w++)
        if (! mark[w])
  	  TopSort(w);
    Print(S);
  } /* main */
  
  

Reachability

Given a directed graph G and a vertex v in G, the reachability problem is to find all vertices in G that can be reached from v by following arcs.

The answer to the reachability problem is the same set of nodes explored from v using depth-first search.

  
  Reachability(vertex v)
  { vertex w;
    for (w = 0; w < N; w++) G[w].mark = 0;
    DFS(v);
    for (w = 0; w < N; w++)
       if (G[w].mark) cout << w;
  } /* Reachability */