Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionii [2012/01/30 23:53] – mugabej | courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionii [2012/01/31 01:40] (current) – mugabej | ||
---|---|---|---|
Line 2: | Line 2: | ||
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(BFS)=== | ||
+ | |||
+ | 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(pseudo-code): | ||
+ | |||
+ | R* = set of connected components (a set of sets)\\ | ||
+ | while there is a node that does not belong 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. 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 | ||
+ | |||
+ | In brief, when trying to efficiently solve problems that involve graph traversal, BFS and DFS are the best options available to the algorithm designer. Both BFS and DFS allows easy and efficient traversals of a graph, which in turn helps solve some problems that involve huge graphs.\\ | ||
+ | |||
+ | This section was also interesting and easy to read,so why not give it a 9/10?Yeah, I give it a 9/10. | ||
+ | |||