Differences

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

--- courses:cs211:winter2018:journals:martinj:3.2.6 [2018/02/07 03:57] – martinj
+++ courses:cs211:winter2018:journals:martinj:3.2.6 [2018/02/07 04:55] (current) – martinj
@@ Line 1: / Line 1: @@
 ====== 3.2-3.6: ======
 ===== Brief summary  =====
-.2 covered graph connectivity and graph traversal, including breadth-first and depth-first searches.
+.2 covered graph connectivity and graph traversal, including breadth-first and depth-first searches, which determine s-t connectivity, or whether or not there is a path between s and t in a given graph. 3.3 covered implementing graph traversals using queues and stacks, but also covered the different ways to represent graphs themselves. 3.4 covered an application of BFS that tested bipartness, and 3.5 covered connectivity in directed graphs. Overall, this section wasn't too difficult for me, as it was pretty readable. However, it did admittedly get progressively more difficult. I honestly think I need more time to let it all sink in before I can conjure up concrete questions to ask.
-Motivations
+===== Algorithms: brief sketches, intuitions, implementations, runtimes =====
+==== Breadth-First Search ====
-Algorithms: brief sketches, intuitions, implementations, runtimes
+Explore outward from s in all possible directions, adding nodes one "layer" at a time.
+Layers
+  * The layer containing a node represents the point in time at which the node is reached.
-Questions:
+  * The first layer of the search is all neighboring nodes of s (nodes that are joined by an edge to s)
+  * Generally speaking, Layer #j+1 contains all nodes that do not belong to an earlier layer and that have an edge to a node in layer #j
-Stuff I want to remember:
+Concepts:
+  * There is a path from s to t IFF t appears in some layer
+  * If there is an edge between two points in the original graph, then those two points differ by at most 1 in the breadth-first search tree
+Worst-case runtime: O(# of vertices)
+=== Depth-First Search ===
+General concept: start from s and try the first edge leading out. Continue this process until you reach a "dead end" = a node for which you had already explored all its neighbors. Then backtrack until you get a node with an unexplored neighbor and continue from there.
+Pseudocode:
+    DFS(u):
+        Mark u as "Explored" and add u to R
+        For each edge (u,v) incedent to u
+            If v is not marked "Explored" then
+                Recursively invoke DFS(v)
+            Endif
+        Endfor
+Concepts:
+  * Node m is an ancestor of node n if n was marked as explored after m (I think)
+  * If x & y are two nodes that are connected by an edge in the original graph, but not connected its BFS tree, one of them is an ancestor of the other
-How readable / interesting the section was:
+===== Stuff I want to remember =====
+There are 2 basic ways to represent graphs:
+  - An adjacency matrix -- requires O(n^2 ) space
+  - An adjacency list representation -- requires only O(m+n) space
+A queue is a set form which we extract elements in FIFO (first in, first out) order = the order in which they were added
+  * Stack = same, but opposite (LIFO)