Differences
This shows you the differences between two versions of the page.
Next revision | Previous revisionNext revisionBoth sides next revision | ||
courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionii [2012/01/30 23:50] – created mugabej | courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionii [2012/01/31 00:12] – mugabej | ||
---|---|---|---|
Line 1: | Line 1: | ||
====== 3.2 Graph Connectivity and Graph Traversal ====== | ====== 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 " | + | 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 " |
+ | |||
+ | ===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< | ||
+ | * L< | ||
+ | * Assuming L< | ||
+ | * For each j≥ 1, layer L< | ||
+ | * 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< | ||
+ | * 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\\ | ||