Chapter 3.3: Implementing Graph Traversal w/Queues and Stacks

The BFS and DFS algorithms differ essentially only in that one uses a queue in its implementation and the other uses a stack.

There are two basic ways to represent a graph: using an adjacency matrix or an adjacency list.

Adjacency Matrix: Consider a graph G=(V,E) with n nodes and assume the set of nodes is V={1,…,n}. An adjacency matrix is an nxn matrix A where A[u,v] is equal to 1 if the graph contains the edge (u,v) and 0 otherwise. If the graph is undirected, A is symmetric with A[u,v]=A[v,u] for all nodes u and v in V. The adjacency matrix allows us to check in O(1) time if a given edge (u,v) is present in the graph. However:

• The matrix takes θ(n^2) space which is not good if the graph has a lot fewer edges than n^2
• Many graph algorithms need to examine all edges incident to a given node v. In an adjacency matrix, this involves considering all other nodes w, and checking the entry A[v,w] to see whether edge (v,w) is present. This takes θ(n) time.

Adjacency List: In this representation, there is a record for each node v, containing a list of all nodes to which v has edges. In other words, we have an array Adj where Adj[v] is a record containing a list of all nodes adjacent to node v. For an undirected graph G=(V,E), each edge e=(v,w) in E occurs on two adjacency lists, node w appears on the list for node v and node v appears on the list for node w.

• The list takes O(n+m) space

A queue is a set from which we extract elements in first-in, first-out (FIFO) order; we select elements in the same order in which they were added. A stack is a set from which we extract elements in last-in, first-out (LIFO) order; each time we select an element, we choose the one that was added most recently. Both queues and stacks can be implemented via a doubly linked list. In both cases, we select the first element in the list, the difference is where we insert a new element. In a queue, we insert a new element at the end of the list as the last element, whereas in a stack we insert a new element in the first position on the list. Doubly linked lists have FIRST and LAST pointers, so insertion can be done in constant time.

• 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 = {}
• While L_i is not empty:
• Initialize and empty list L[i+1]
• For each node u in L[i]
• Consider each edge (u,v) incident to u
• If Discovered[u] = false then:
• Set Discovered[v] = true
• Add edge (u,v) to the tree T
• Add v to the list L[i+1]
• End if
• End for
• Increment the layer counter i by 1
• End while

This implementation runs in O(n+m) time.

• 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 then:
• Set Explored[u] = true
• For each edge (u,v) incident to u
• Add v to the stack S
• End for
• End if
• End while

This implementation runs in O(n+m) time.