### 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: like breadth-first search in a tree, we search as broadly as possible by visiting a node, and then immediately visiting all nodes adjacent to that node.

• depth-first search: like depth-first search in a tree, we search as deeply as possible by visiting a node, and then recursively performing depth-first search on each adjacent node.

### 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.

• if dfs(v) causes a recursive call dfs(u) then u is a child of v in the tree.

• the children of v appear left to right in the tree in the order they are marked.

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;
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.

• Such an arc represents a cycle created by following the tree edges from v to u (which must be possible since v is an ancestor of u), and then the edge u to v to complete the cycle.

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.

• If you visited u first, you would have numbered v first (in postorder), and u.postorder > v.postorder. So you must have visited v first.

• If DFS(v) does not visit u, then v.postorder < u.postorder.

• Since DFS(v) does visit u, the cycle consists of the path produced by DFS(v) to u, then u to v using the edge (u,v).

### Testing for Cycles: The Algorithm

```
boolean Acyclic(int N, graph &G)
{ vertex u,v;
dfsForest();
for (u = 0; u < N; u++) {
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;
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;
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 */

```