Differences

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

--- courses:cs211:winter2018:journals:mccaffreyk:home:3 [2018/02/06 04:49] – mccaffreyk
+++ courses:cs211:winter2018:journals:mccaffreyk:home:3 [2018/02/06 05:00] (current) – [Section 3.6: Directed Acyclic Graphs and Topological Ordering] mccaffreyk
@@ Line 23: / Line 23: @@
 ==== Section 3.6: Directed Acyclic Graphs and Topological Ordering ====
+A directed acyclic graph is a directed graph with no cycles. The structure of these is often much richer than non-directed graphs without cycles(more edges). These DAGS are naturally ordered and usually applied to systems such as college courses where one cannot backtrack directly. The comparative classification of nodes in a DAG is called a "topological ordering". In a topological ordering, all edges must "point forward". If a graph has a topological ordering than it is a DAG. Further, is a graph is a DAG than it must have a topological ordering. The lowest node of any DAG has no incoming edges. There can also be other nodes with no incoming edges. Computing a topological ordering for a DAG takes O(n^2) time but may take O(n+m) only for very thin, non-dense graphs.