3.3Implementing Graph Traversal Using Queues and Stacks

A graph can be represented as either an adjacency matrix or an adjacency list. with a graph G = (V,E), the number of nodes |V| is denoted as n and the number of edges |E| is denoted as m. When discussing the representations of graphs, our aim is to get a representation that allows us to implement the graph in a polynomial running time. The number of edges m is always less than or equal to n2. Since most of graphs are connected, the graphs considered in the discussion of the representation of graphs have at least m≥ n-1 edges. The goal we have in the implementation of graphs is O(m+n), and is called linear time.


Some Definitions:

Queues and Stacks

Implementation and analysis of the BFS and the DFS

BFS(s):
Discovered[v] = false, for all v
Discovered[s] = true
L[0] = {s}
layer counter i = 0
BFS tree T = {}
while L[i] != {}

L[i+1] = {}
For each node u ∈ L[i]
Consider each edge (u,v) incident to u
if Discovered[v] == false then
Discovered[v] = true
Add edge (u, v) to tree T
Add v to the list L[i + 1]

Endif

Endfor

end while

This implementation of the BFS takes O(m+n) if the graph is given by the adjacency list representation.

DFS(s):
Initialize S to be a stack with one element s
Explored[v] = false, for all v
Parent[v] = 0, for all v
DFS tree T = {}
while S != {}

Take a node u from S
if Explored[u] = false
Explored[u] = true
Add edge (u, Parent[u]) to T (if u ≠ s)
for each edge (u, v) incident to u
Add v to the stack S
Parent[v] = u

Endfor

Endif

end while

This implementation of the DFS takes O(m+n) if the graph is given by the adjacency list representation.

Thus when using a DFS or a BFS, one can easily implement graph traversals in linear time(O(m+n)).

This section was interesting too, I give it an 8/10.