**__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.