Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:donohuem:chapter3 [2018/02/07 02:07] – [3.5 Connectivity in Directed Graphs] donohuem | courses:cs211:winter2018:journals:donohuem:chapter3 [2018/02/07 02:17] (current) – donohuem | ||
|---|---|---|---|
| Line 18: | Line 18: | ||
| ===== 3.5 Connectivity in Directed Graphs ===== | ===== 3.5 Connectivity in Directed Graphs ===== | ||
| When representing directed graphs, we use a modified version of the adjacency list. The search algorithms (BFS and DFS) for undirected graphs are almost the same for directed graphs with slight exceptions. For example, a BFS on nodes and s and t may reveal that a path exists between from s to t AND from t to s. For a directed graph, however, it is not a guarantee that t may have a path to s. An important notion is this section is Strong Connectivity. A graph is strongly connected if every two nodes are mutually reachable -- a path exists from nodes s to t and t to s. An algorithm to test whether a directed graph is strongly connected can be done in linear time. Overall, the readability of this section was 7/10. | When representing directed graphs, we use a modified version of the adjacency list. The search algorithms (BFS and DFS) for undirected graphs are almost the same for directed graphs with slight exceptions. For example, a BFS on nodes and s and t may reveal that a path exists between from s to t AND from t to s. For a directed graph, however, it is not a guarantee that t may have a path to s. An important notion is this section is Strong Connectivity. A graph is strongly connected if every two nodes are mutually reachable -- a path exists from nodes s to t and t to s. An algorithm to test whether a directed graph is strongly connected can be done in linear time. Overall, the readability of this section was 7/10. | ||
| + | |||
| + | |||
| + | ===== 3.6 Directed Acyclic Graphs and Topological Ordering ===== | ||
| + | A DAG is simply a directed graph that has no cycles. DAGs are common structures in computer science. A relatable example is a graph showing prerequisite course requirements for a major, with each node representing a course. If a graph is a DAG, then it must have a topological ordering. A topological ordering is a organization of a graph such that all edges point from left to right. We can use an algorithm that computes a topological ordering for a DAG. First we must find a node with no incoming edges, order it first, then delete it from the graph. We then recursively call the algorithm. The run time for this algorithm is ostensibly O(n^2) because finding a node with no incoming edges takes O(n) time in addition to recursively running the algorithm for n iterations. However, we can reduce this run time to O(m + n) by more efficiently finding a node with no incoming edges. Overall, the readability of this section was 6/10. | ||
