Differences

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

--- courses:cs211:winter2018:journals:martinj:3.2.6 [2018/02/07 04:07] – martinj
+++ courses:cs211:winter2018:journals:martinj:3.2.6 [2018/02/07 04:55] (current) – martinj
@@ Line 2: / Line 2: @@
 ===== Brief summary  =====
-.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.
+.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 ====
@@ Line 16: / Line 14: @@
   * 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.
-===== Questions =====
+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
 ===== Stuff I want to remember =====
+There are 2 basic ways to represent graphs:
-===== How readable / interesting the section was =====
+  - 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)