Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision | ||
courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionii [2012/01/31 00:12] – mugabej | courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionii [2012/01/31 01:35] – mugabej | ||
---|---|---|---|
Line 3: | Line 3: | ||
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=== | + | ===Breadth-First Search(BFS)=== |
Using this method, we explore outward from the the (root) node s in all possible directions, going one layer at a time.\\ | Using this method, we explore outward from the the (root) node s in all possible directions, going one layer at a time.\\ | ||
Line 16: | Line 16: | ||
==Algorithm== | ==Algorithm== | ||
- | Brief sketch:\\ | + | Brief sketch(pseudo-code):\\ |
R* = set of connected components (a set of sets)\\ | R* = set of connected components (a set of sets)\\ | ||
while there is a node that does not belong to R*\\ | 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\\ | 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. Great application: | ||
+ | ===Depth-First Search(DFS)=== | ||
+ | |||
+ | This algorithms consists in going through a graph as far as possible, and only retreating(or backtracking)when necessary. With this implementation, | ||
+ | * Similarities with BFS: They both build the connected component containing s, and achieve qualitatively similar levels of efficiency. In both implementations, | ||
+ | * Differences with BFS: DFS visits the nodes in a different order:it probes its way down long paths, potentially getting very far from s, before backtracking to explore nearer nodes. | ||
+ | * Also, the trees they both produce have different structures: DFS trees tend to be narrow and deep while BFS trees are as short as possible. | ||
+ | |||
+ | ==Algorithm== | ||
+ | |||
+ | DFS(u): | ||
+ | Mark u as " | ||
+ | For each edge (u,v) incident to u: | ||
+ | >>>>> | ||
+ | >>>>>>>>> | ||
+ | >>>>> | ||
+ | Endfor | ||
+ | |||
+ | |||
+ | |||
+ | |||