====== 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<sub>2</sub>. 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<sup>2</sup>) space.However, when the graph has many fewer edges than n<sup>2</sup>, 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<sup>2</sup> 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<sup>2</sup>) space
    * An Adjacency list takes O(m+n) space.
    * In the Adjacency list, it takes O(//n<sub>v</sub>//) 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<sub>v</sub>// of a node v is the number of incident edges it has.
  * The length of the list at Adj[v] is //n<sub>v</sub>//
  * The sum of the degrees in a graph = **//2m//**


=== Queues and Stacks===

  * 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
 ==Implementation and analysis of the BFS and the DFS ==

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