3.3: Implementing Graph Traversal Using Queues and Stacks

Two basic ways to represent graphs: adjacency matrix and adjacency list. The adjacency matrix representation of a graph requires O(n^2) space, while the adjacency list representation requires only O(m+n).

Queues and Stacks

A queue is a set from which we extract elements in FIFO order. While a stack is a set from which we extract elements in LIFO order. Both queues and stacks can be easily implemented via a doubly linked list.

Implementing Breadth-First Search

BFS(s):
 Set Discovered[s] = true and Discovered[v] = false for all other v
 Initialize L[0] to consist of the single element s.
 Set the layer counter i=0
 Set the current BFS tree T = emptyset
 While L[i] is not empty
   Initialize an empty list L[i+ 1]
   For each node u that is an element of L[i]
     Consider each edge (u,v) incident to u
     If Discovered[v] = false 
       Set Discovered[v] = true
       Add edge (u,v) to tree T
       Add v to the list L[i+1]
  increment layer counter i by 1

The above implementation of the BFS algorithm runs in the time O(m + n) (edges + vertices), if the graph is given by the adjacency list representation.

Implementing Depth-First Search

The main difference in DFS is that we only set Explored[v] to be true when we scan v's incident edges, while BFS sets Discovered[v] to true as soon as v is first discovered.

DFS(s):

 Initialize S to be a stack with one element s
 While S is not empty
   Take a node u from S
   If Explored[u] = false 
     Set Explored[u] = true
     For each edge (u,v) incident to u
       Add v to the stack S
       

The above algorithm implements DFS in the sense that it visits the nodes in exactly the same order as the recursive DFS procedure in the previous section. (runs in O(m+n) time).

Finding the Set of All Connected Components

BFS and DFS spend work only on edges and nodes in the connected component containing the starting node. BOTH RUN AT O(m+n).

Pretty interesting, very useful algorithms. 10/10.