Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionii [2012/01/30 23:50] – created mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionii [2012/01/31 00:13] – mugabej
@@ Line 1: / Line 1: @@
 ====== 3.2 Graph Connectivity and Graph Traversal ======
-This section aims at answering the question of if there is a path from a node s to another node t, where s and t are node in a graph G=(V,E). The problem is called "determining s-t connectivity".
+This section aims at answering the question of if there is a path from a node s to another node t, where s and t are node in a graph G=(V,E). The problem is called "determining s-t connectivity". Although it can be pretty easy to answer this problem for small graphs, it become more painful for reasonably sized graph. That's why we need a more elegant and efficient way to solve the problem in case we have a fairly big graph. Breadth-First Search and Depth-First algorithms are the most efficient algorithms commonly used to solve this problem.
+===Breadth-First Search===
+Using this method, we explore outward from the the (root) node s in all possible directions, going one layer at a time.\\
+  * L<sub>0</sub> is the set consisting of just the node s
+  * L<sub>1</sub> consists of all nodes neighbors of s
+  * Assuming L<sub>1</sub>,...,L<sub>j</sub> are defined, L<sub>j+1</sub> consists of all nodes that do not belong to an earlier layer and have an edge to an earlier layer L<sub>j</sub>
+  * For each j≥ 1, layer L<sub>j</sub> produced by BFS consists of all nodes at distance exactly j from s. There is a path from s to t if and only if t appears in some layer.
+  * 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\\