Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |
| courses:cs211:winter2014:journals:colin:chapter3 [2014/02/02 23:38] – mohnacsc | courses:cs211:winter2014:journals:colin:chapter3 [2014/02/02 23:55] (current) – mohnacsc |
|---|
| |
| A directed graph in adjacency list representation has two associated lists for each node: nodes to which it has edges and nodes from which it has edges. A graph is strongly connected (or mutually agreeable) if, for every two nodes u and v, there is a path from u to v and a path from v to u. If u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable. For any two nodes s and t in a directed graph, their strong components are either identical or disjointed. It is possible to compute the strong components for all nodes in a total time of O(m+n). | A directed graph in adjacency list representation has two associated lists for each node: nodes to which it has edges and nodes from which it has edges. A graph is strongly connected (or mutually agreeable) if, for every two nodes u and v, there is a path from u to v and a path from v to u. If u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable. For any two nodes s and t in a directed graph, their strong components are either identical or disjointed. It is possible to compute the strong components for all nodes in a total time of O(m+n). |
| | |
| | |
| | ==== 3.6 - Directed Acyclic Graphs and Topological Ordering ==== |
| | |
| | If a directed graph has no cycles it is a directed acyclic graph (DAG). They can be used to encode precedence relations or dependencies in a natural way. A topological ordering of graph G is an ordering of its nodes as v(1), v(2), …, v(n) so that for every edge (v(i), v(j), we have i < j. All edges point forward in the ordering. If G has a topological ordering, then G is a DAG (and vice versa). |
| | |
| | In every DAG G, there is a node v with no incoming edges. This is the beginning of our algorithm. Then, recursively compute the topological ordering of G-{v} and append the order. The run time of this algorithm is O(n^2). |
| | |
| | |
| | === Discussion === |
| | |
| | With the expansion of the BFS and DFS applications, there is more of an understanding of how algorithm design follow strict patterns and rules are used to analyze increasingly complex structures. In previous courses, the tree structure was fairly unexplored but now is seen as a very complex and tricky structure. I am worried that directed and undirected graphs might become more complicated in future sections but have not had too much trouble with them too far. |
