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
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 */
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).
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)
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)
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 */
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).
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)
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.
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 */
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.
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 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 */
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 */
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 */