Differences

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

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