Differences

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

--- courses:cs211:winter2018:journals:holmesr:section_3.3 [2018/02/05 19:33] – created holmesr
+++ courses:cs211:winter2018:journals:holmesr:section_3.3 [2018/02/06 03:41] (current) – holmesr
@@ Line 2: / Line 2: @@
 Breadth-First Search and Depth-First search often produce quite different trees, but their mechanics are very similar and in fact their essential difference is one's using a queue versus the other's using a stack.
+Breadth-First Search works in O(//m//+//n//) time to assemble the Breadth-First search tree. It does this by making a List L[i] with i = 0, so tjis only contains the root node //s//. It then makes an empty list L[i + 1] and adds the undiscovered nodes enumerated in adjacency lists of each node in L[i] and marks those nodes as discovered. Finally, it increments i to advance the loop. This runs in O(//n//+//m//) because besides setting up the lists in n time, a for loop runs in m time considering each edge. It runs in m time because it must consider to degree of each node, or 2m.
+Depth-First Search makes a stack which initially only contains the root node //s//. It then enters a loop which takes the first item off the stack, marks it as explored, adds all its adjacent nodes to the stack and repeats the loop until the stack is empty. This algorithm also runs in O(//n//+//m//) time since everything within the loop runs in constant time and the loop executes as many times as the sum of the degree of all the nodes in the graph, which is 2m.
+The one thing I didn't understand about this chapter is the how a BFS could be implemented using a queue. The chapter promised that this was true but didn't really explain how, at least in my eyes.