Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionii [2012/01/31 00:17] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionii [2012/01/31 01:40] (current) – 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 "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===
+===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.\\
@@ Line 16: / Line 16: @@
 ==Algorithm==
-Brief sketch:\\
+Brief sketch(pseudo-code):\\
 R* = set of connected components (a set of sets)\\
@@ Line 28: / Line 28: @@
 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.\\
+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: Finding the shortest path.\\
-==Depth-First Search==
+===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, we keep track of the nodes we have already explored so that we may be able to backtrack when necessary.
+  * Similarities with BFS: They both build the connected component containing s, and achieve qualitatively similar levels of efficiency. In both implementations, nontree edges can only connect ancestors to descendants.
+  * 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 "Explored" and add u to R \\
+For each edge (u,v) incident to u:
+>>>>>if v is not marked "Explored" then
+>>>>>>>>>Recursively invoke DFS(u)
+>>>>>Endif
+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.