15 Apr 1996

Outline

• BFS - breadth-first search
• DFS - depth-first search

Breadth-first search

1. Start the search at some node v. Visit v.
2. Visit all nodes at distance 1 from v.
3. Visit all nodes at distance 2 from v.
4. ...

As an example, say we start at v in this graph:

  v---a
  |\  |\
  c-i-d-b-e
  |   |\
  f---g-h
        |
        j

1. visit v
2. visit a, i, c
3. visit b, d, f
4. visit e, g, h
5. visit j

This is an algorithm:

1. Label each node either 1) visited, 2) on fringe, or 3) unknown. Also, label each node with its distance from v.
2. Initially, label all nodes except v "unknown". Label v "on fringe", and put v in a queue. Initially, give node v distance 0, give all other nodes distance infinity.
3. The queue will hold all nodes labeled on fringe -- neighbors of visited nodes that have not themselves been visited. Once a node enters fringe, its final distance is known.
4. Remove nodes from the queue one at a time.
5. When a node u is removed, label it visited. Add any neighbors of u that are not visited and not on fringe to the queue. Label the neighbors "on fringe", and give them distance dist(u)+1.

Going back to our example:

Queue:

v     (remove v; a, i, c move to fringe)
0

aic   (remove a; b, d move to fringe)
111

icbd  (remove i; d already on fringe)
1122

cbd   (remove c; f moves to fringe)
122

bdf   (remove b; e moves to fringe)
222

dfe   (remove d; g, h move to fringe)
223

fegh  (remove f)
2333

egh   (remove e)
333

gh    (remove g; j moves to fringe)
33

hj    (remove h)
34

j     (remove j)
4

Notice that the nodes in the queue are always ordered by distance. Also, notice that nodes are visited in order of distance from v:

v aic bdf egh j
0 111 222 333 4

Now we can implement it in C++:

// Assumes adjacency list rep. from Assignment 2
// Assumes v is vertex 0.

label[0] = ON_FRINGE;
dist[0] = 0;
for(i = 1; i < n; i++) {
    label[i] = UNKNOWN;
    dist[i] = INFINITY;
}

Queue q;
q.insert(0);

while(q.length() > 0) {
    int current = q.remove();
    label[current] = VISITED;
    node *current_node = maze->find_node_by_number(current);
    for(list_element *ptr = current_node->neighbors; ptr; ptr = ptr->next) {
        if(label[ptr->neighbor] == UNKNOWN) {
            label[ptr->neighbor] = ON_FRINGE;
            dist[ptr->neighbor] = dist[current] + 1;
            q.insert(ptr->neighbor);
        }
    }
}

 0     1
  v---a
  |\  |\
 1c-i-d-b-e
  | 12|\ 2 3
  f---g-h3
 2   3  |
        j4

Depth-first search

The differences from the breadth-first algorithm:

• Replace the queue with a stack.
• Label nodes either VISITED or NOT_VISITED.
• Don't worry about distances.
• Allow a node to appear more than once on the stack.

  v---a
  |\  |\
  c-i-d-b-e
  |   |\
  f---g-h
        |
        j

v     (remove v, add a, i, c)
cia   (remove c, add f)
fia   (remove f, add g)
gia   (remove g, add d, h, j)
jhdia (remove j)
hdia  (remove h, add d again since it hasn't been visited)
ddia  (remove d, add b)
bdia  (remove b, add e)
edia  (remove e)
dia   (remove d; already visited, so don't add neighbors)
ia    (remove i)
a     (remove a)

Here is a depth-first search tree:

  v---a
  |\
  c i d-b-e
  |    \
  f---g-h
        |
        j

void
dfs(int current) {
    if(label[current] == VISITED) return;
    label[current] = VISITED;

    node *current_node = maze->find_node_by_number(current);
    for(list_element *ptr = current_node->neighbors; ptr;
            ptr = ptr->next) {
        dfs(ptr->neighbor);
    }
}

for(i = 0; i < n; i++) {
    label[i] = NOT_VISITED;
}

dfs(0);