Differences

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

--- courses:cs211:winter2012:journals:virginia:chapter3 [2012/02/16 02:53] – [Section 1: Basic Definitions and Applications] lovellv
+++ courses:cs211:winter2012:journals:virginia:chapter3 [2012/02/16 03:06] (current) – lovellv
@@ Line 52: / Line 52: @@
 The **strong component** containing s in a directed graph is the set of all v such that s and v are mutually reachable.  The strong component is similar to the connected component for an undirected graph.  Like the connected component, strong components are either identical or disjoint.
 Readability: 8
+===== Section 6: Directed Acyclic Graphs and Topological Orderings =====
+A special type of directed graph that contains no cycles is a **directed acyclic graph** (DAG).  DAGs can be used to represent precedence relations or dependencies.  One natural problem relating to DAGs is how to create a **topological ordering** (an ordering in which all edges point forward) from a DAG.  This is the equivalent to finding the order in which we may do tasks which depend on each other.  It is easy to see if a graph has a topological ordering, it is a DAG, but it is not obvious every DAG has a topological ordering.
+In fact, every DAG does have a topological ordering. We can find it by finding a node with no incoming edges, ordering it next in our topological ordering, deleting it from our graph, and repeating until we have added every node.  This algorithm has O(m+n) run time. (p 103)
+Readability: 8