Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2018:journals:mccaffreyk:home:3 [2018/02/06 04:48] – [Section 3.5: Connectivity in Directed Graphs] mccaffreyk | courses:cs211:winter2018:journals:mccaffreyk:home:3 [2018/02/06 05:00] (current) – [Section 3.6: Directed Acyclic Graphs and Topological Ordering] mccaffreyk |
|---|
| |
| Directed graphs are one directional: edges must go from node a to node b and cannot go back from node b to node a. We still use adjacency lists for directed graphs but maintain two lists of edges: a to list and a from list. Searching is basically the same(time, techniques, etc) as in non-directed graphs, but must only follow nodes according to inherent direction. If a directed graph is strongly connected, every pair of nodes a and b must have paths between them (path from a to b and from b to a). Not always the case here. This has transitive properties: if a and b are mutually reachable, nodes b and c are mutually reachable, a and c must also be mutually reachable. This allows us to conclude that "strong components" of graphs are either identical or completely different(disjoint). | Directed graphs are one directional: edges must go from node a to node b and cannot go back from node b to node a. We still use adjacency lists for directed graphs but maintain two lists of edges: a to list and a from list. Searching is basically the same(time, techniques, etc) as in non-directed graphs, but must only follow nodes according to inherent direction. If a directed graph is strongly connected, every pair of nodes a and b must have paths between them (path from a to b and from b to a). Not always the case here. This has transitive properties: if a and b are mutually reachable, nodes b and c are mutually reachable, a and c must also be mutually reachable. This allows us to conclude that "strong components" of graphs are either identical or completely different(disjoint). |
| | |
| | ==== 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. |
