Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapterthreesectioniii [2012/01/31 02:39] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterthreesectioniii [2012/01/31 02:48] (current) – mugabej
@@ Line 27: / Line 27: @@
     * 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 of the BFS and the DFS ==
+ ==Implementation and analysis of the BFS and the DFS ==
   * BFS: \\
-BFS(s):
+BFS(s):\\
-Discovered[v] = false, for all v
+Discovered[v] = false, for all v\\
-Discovered[s] = true
+Discovered[s] = true\\
-L[0] = {s}
+L[0] = {s}\\
-layer counter i = 0
+layer counter i = 0\\
-BFS tree T = {}
+BFS tree T = {}\\
-while L[i] != {}
+while L[i] != {}\\
 >>>>>L[i+1] = {}
 >>>>>For each node u ∈ L[i]
@@ Line 49: / Line 49: @@
 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.