Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:cohene:home:chapter3 [2018/02/07 00:43] – [3.5: Connectivity in Directed Graphs] cohene | courses:cs211:winter2018:journals:cohene:home:chapter3 [2018/02/07 00:55] (current) – [3.6: Directed Acyclic Graphs and Topological Ordering] cohene | ||
|---|---|---|---|
| Line 38: | Line 38: | ||
| A graph is strongly connected if, for two nodes u and v, u and v have a path as well as v and u. u and v are mutually reachable if it is strongly connected. There are several properties that can be derived from this. First, if u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable. We can check in linear time if a directed graph is strongly connected. We can define the strong component containing a node s in a directed graph to be the set of all v such that s and v are mutually reachable. Furthermore, | A graph is strongly connected if, for two nodes u and v, u and v have a path as well as v and u. u and v are mutually reachable if it is strongly connected. There are several properties that can be derived from this. First, if u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable. We can check in linear time if a directed graph is strongly connected. We can define the strong component containing a node s in a directed graph to be the set of all v such that s and v are mutually reachable. Furthermore, | ||
| ===== 3.6: Directed Acyclic Graphs and Topological Ordering===== | ===== 3.6: Directed Acyclic Graphs and Topological Ordering===== | ||
| + | If a directed graph has no cycles it is considered a directed acyclic graph (DAG). DAGs can be used for precedence relations or dependencies. Given a set of tasks with dependencies, | ||
| + | We look here to check if every DAG has a topological ordering. To do so, we need to find which node goes at the beginning of a topological ordering. In every DAG there must be a node with no incoming edges, which will be the starting node. This will help us build our topological ordering. Once we remove the starting node, we must find the next node with no incoming edges. If we repeat this pattern, we will eventually build our order. This section int he textbook really helps to clarify our discussion of this topic in class. In this algorithm, finding a node v with no incoming edges and deleting it will be done in O(n), and the algorithm itself runs n times, so the total running time is O(n^2). By iteratively deleting nodes with no incoming edges we can achieve a running time of O(m+n). | ||
