Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionii [2012/01/31 00:05] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionii [2012/01/31 00:17] – mugabej
@@ Line 12: / Line 12: @@
   * BFS produces a tree T rooted at s on the set of nodes reachable from s.
   * For a BFS tree T, if x and y are nodes in T belonging to layers L<sub>i</sub> and L<sub>j</sub> respectively, and if (x,y) is an edge of G, then i and j differ by at most 1
+  * The set of nodes discovered by the BFS algorithm is exactly those reachable from the starting node s: this set R is called the set of //connected component of G containing s//.
+==Algorithm==
+Brief sketch:\\
+R* = set of connected components (a set of sets)\\
+while there is a node that does not belong to R*\\
+>>>>>select s not in R*\\
+>>>>>R = {s}\\
+>>>>>while there is an edge (u,v) where u∋R and v∉R\\
+>>>>>>>>>>add v to R\\
+>>>>>end while\\
+>>>>>Add R to R*\\
+end while\\
+The R produced at the end of the algorithm is the //connected component of G containing s//. The BFS algorithms is usually used when we need to order nodes we visit in successive layers based on their distance from s.\\
+===Depth-First Search===