Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:jeanpaul:chapterthreesectioniii [2012/01/31 02:00] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterthreesectioniii [2012/01/31 02:48] (current) – mugabej
@@ Line 2: / Line 2: @@
 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.
@@ Line 7: / Line 9: @@
     * 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.