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 n₂. 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:

• Adjacency matrix: it's an n X n matrix A where A[u,v] is equal to 1 if the graph contains the edge (u,v), and 0 otherwise. This representation allows us to represent graphs in O(1) time if a the edge (u,v) is in the graph.
• Disadvantages:
  • The representation takes Θ(n²) space.However, when the graph has many fewer edges than n², more compact (and better) representations are possible
  • Many graph algorithms need to examine all edges incident to a given node v. With the adjacency matrix, this operation takes Θ(n) time. More efficient algorithms exist solve this problem.
• Adjacency list: With this representation, there is record for each node v, containing a list of the nodes to which v has edges. It used when the graphs have less than n² edges.
• With this representation we have an array Adj, where Adj[v] contains a record of all nodes adjacent to the node v.
• Comparison of the Adjacency list and the Adjacency matrix:
  • Since an Adjacency matrix requires an n X n matrix, it is O(n²) space
  • An Adjacency list takes O(m+n) space.
  • In the Adjacency list, it takes O(n_v) time to check if a particular edge (u,v) is in the graph, while the same operation takes O(1) time for an adjacency matrix.
• The degree n_v of a node v is the number of incident edges it has.
• The length of the list at Adj[v] is n_v
• The sum of the degrees in a graph = 2m

• With A queue, we use the First in, First Out(FIFO) concept
  • The new element is added to the end of the list
• For a stack, we use the Last in, First Out(LIFO) concept
  • The new element is added at the front of the list
• In both implementations, the doubly linked lists used maintain a FIRST and a LAST pointers which allows constant time insertions

• BFS:
  

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:
  

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.