Differences

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

--- courses:cs211:winter2014:journals:deirdre:chapter3 [2014/02/12 04:21] – [Section 3.5 - Connectivity in Directed Graphs] tobind
+++ courses:cs211:winter2014:journals:deirdre:chapter3 [2014/02/12 04:40] (current) – [Section 3.6 - Directed Acyclic Graphs and Topological Ordering] tobind
@@ Line 149: / Line 149: @@
 ====== Section 3.5 - Connectivity in Directed Graphs ======
-Remember: in directed graphs, the edge //(u,v)// has a direction: it goes from //u// to //v/. (relationship is asymmetric)
+Remember: in directed graphs, the edge //(u,v)// has a direction: it goes from //u// to //v//. (relationship is asymmetric)
 To represent a dg, we use aversion of the adjacency list representation. Now, instead of each node having a single list of neighbors, each node has two lists associated with it: one list consists of nodes to which it has edges and a second list consists of nodes from which it has edges.
@@ Line 164: / Line 164: @@
 For any two nodes //s// and //t// in a dg, their strong components are either identical or disjoint.
 ====== Section 3.6 - Directed Acyclic Graphs and Topological Ordering ======
+If an undirected graph has no cycles, then each of its connected components is a tree. But it's possible for a dg to have no cycles and still "have a very rich structure". If a dg has no cycles, we call it a DAG (directed acyclic graph).
+**The Problem**
+.18 If G has a topological ordering, then //G// is a DAG.
+Does every DAG have a topological ordering? How do we find one efficiently?
+**D and A the Algorithm**
+(Spoiler alert: The converse of 3.18 is true.) Which node do we put at the beginning of the topological ordering? Such a node would need to have no incoming edges. (In every DAG G, there is a node v with no incoming edges)
+Algorithm:
+ To compute a topological ordering of G:
+ Find a node v with no incoming edges and order it first
+ Delete v from G
+ Recursively compute a topological ordering of G-{v} and append this order after v
+We can achieve a running time of //O(m+n)// by iteratively deleting nodes with no incoming edges. We can do this efficiently by declaring nodes "active" and maintaining:
+ - for each node //w//, the number of incoming edges that //w// has from active nodes;
+ - the set S of all active nodes in //G// that have no incoming edges from other active nodes.
+At the start, all nodes are active. This allows us to keep track of nodes that are eligible for deletion.
+This section was an 8 to read. I must have been tired in class this day or else we didn't cover it very much because the acyclic stuff makes way more sense now.