====== 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.

===== Implementing BFS =====
  * 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.

===== Implementing DFS =====
  * 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.