Differences

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

--- courses:cs211:winter2018:journals:bairdc:chapter3 [2018/02/07 00:56] – bairdc
+++ courses:cs211:winter2018:journals:bairdc:chapter3 [2018/02/07 04:58] (current) – bairdc
@@ Line 10: / Line 10: @@
 ===== 3.2 – Graph Connectivity and Graph Traversal =====
+There are 2 algorithms for graph traversal: Breadth-First Search (BFS) and Depth-First Search (DFS). BFS can be thought of as starting at a node s and flooding "the graph with an expanding wave that grows to visit all nodes that it can reach". Layers of the graph can be defined as L1,...,Ln. Both BFS and DFS have qualitatively similar levels of efficiency.
+BFS:
+<code>
+R will consist of nodes to which s has a path
+R = {s}
+while there is an edge (u,v) where u∈R and v∉R
+    add v to R
+</code>
+Depth first traversal can be thought of as being in a maze of rooms. You'd start from s and try the first path leading out of it to a different room. You'd keep following the path until you hit a dead end, in which case you'd backtrack to a room with an unexplored neighbor and resume from there.
+DFS:
+<code>
+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
+            DFS(v)
+</code>
+This section was very readable, and I'd give it a 9/10 on both enjoyability and readability.
+===== 3.3 – Implementing Graph Traversal Using Queues and Stacks =====
+BFS uses a queue (FIFO) and DFS uses a stack (LIFO). Adjacency matrixes use Theta(n^2) space, O(1) lookup, and examining adjacent edges in Theta(n). Adjacency lists require only O(m+n) space. You have pointers of length n to set up the lists. Total length of all lists is O(2m) because of the 2 occurrences of nodes (edge connects 2). Sum of the degrees in a graph comes out to be 2m.
+BFS:
+<code>
+BFS(s, G):
+  Discovered[v] = false, for all v
+  Discovered[s] = true
+  L[0] = {s}
+  layer counter i = 0
+  BFS tree T = {}
+  while L[i] != {}
+    L[i+1] = {}
+    for each node u ∈ L[i]
+      Consider each edge (u,v) incident to u
+      if Discovered[v] == false then
+        Discovered[v] = true
+        Add edge (u, v) to tree T
+        Add v to the list L[i + 1]
+    i+=1
+</code>
+DFS:
+<code>
+DFS(s, G):
+  Initialize S to be a stack with one element s
+  Explored[v] = false, for all v
+  Parent[v] = 0, for all v
+  DFS tree T = {}
+  while S != {}
+    Take a node u from S
+    if Explored[u] = false
+      Explored[u] = true
+      Add edge (u, Parent[u]) to T (if u ≠ s)
+      for each edge (u, v) incident to u
+        Add v to the stack S
+        Parent[v] = u
+</code>
+Overall I'd give this section a 7/10 on readability and interestingness. I thought it was a bit hard at times to follow the algorithms, but I got everything after a few read throughs.
+===== 3.4 – Testing Bipartiteness: An Application of Breadth-First Search =====
+A bipartite graph is one in which "the node set V can be partitioned into sets X and Y in such a way that every edge has one end in X and the other end in Y". Or, one in which every edge has one red end and one blue end. If a graph is bipartite, then it can't contain an odd cycle. Also, odd cycles are their only obstacles. The coloring algorithm to test for a bipartite graph is essentially BFS, moving outward from s and coloring nodes as they are encountered.
+Overall I'd give this section a 10/10 on readability and interestingness. It was very concise and made complete sense.
+===== 3.5 – Connectivity in Directed Graphs =====
+When we represent directed graphs, each node will have 2 lists: one with nodes to which it has edges, and one from which it has edges. Something to note is that BFS and DFS are almost the same in directed graphs as they are in undirected graphs. A graph is strongly connected if, for every 2 nodes u and v, there is a path from u to v and one from v to u. 2 nodes are mutually reachable if there is a path from u to v and v to u, so a graph is strongly connected if every two nodes are mutually reachable. If u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable. Also, for any 2 nodes s and t in a directed graph, their strong components are either identical or disjoint.
+Overall I'd give this section a 10/10 on readability and interestingness. It was very concise and intuitive.
+===== 3.6 – Directed Acyclic Graphs and Topological Ordering =====
+Directed Acyclic Graphs (DAGs) are common in Computer Science because many kinds of dependency networks use them. A topological ordering of G is an ordering of its nodes as v1, v2, ..., vn so that for every edge (vi, vj), we have i < j. If G has a topological ordering, then G is a DAG. The converse of this holds as well. Also, in every DAG G, there is a node v with no incoming edges. You can repeatably remove v and find another v to find the topological order.
+Overall I'd give this section a 9/10 on readability and interestingness.