Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:patelk:chapter3 [2018/02/05 05:36] – [3.4 Testing Bipartiteness: An Application of Breadth-First Search] patelk | courses:cs211:winter2018:journals:patelk:chapter3 [2018/02/05 05:40] (current) – [3.6 Directed Acyclic Graphs and Topological Ordering] patelk | ||
|---|---|---|---|
| Line 201: | Line 201: | ||
| * Compute the strong components for all nodes: O(m+n) | * Compute the strong components for all nodes: O(m+n) | ||
| + | ==== Personal Thoughts ==== | ||
| + | |||
| + | Again, this section was not very difficult to understand and most of it makes sense. I would like to talk a little bit more about strong connectivity in class. The concept makes sense, but I would like to learn more about why it is useful/ | ||
| + | Readability: | ||
| + | Interesting: | ||
| ===== 3.6 Directed Acyclic Graphs and Topological Ordering===== | ===== 3.6 Directed Acyclic Graphs and Topological Ordering===== | ||
| Line 218: | Line 223: | ||
| * Thus, in every DAG G, there is a node with no incoming edges | * Thus, in every DAG G, there is a node with no incoming edges | ||
| * If this is not true, then there is a cycle, so it is not a DAG | * If this is not true, then there is a cycle, so it is not a DAG | ||
| - | * | + | |
| {{: | {{: | ||
| Line 234: | Line 239: | ||
| * This leads to constant work per edge | * This leads to constant work per edge | ||
| + | ==== Personal Thoughts ==== | ||
| + | |||
| + | This section contained information that I had not yet been exposed to. However, most of the section was very intuitive. Cycles are not a very difficult concept so it makes sense why a DAG cannot have a cycle. This is my first time, as far as I remember, being exposed to DAGs, so it will be interesting to see how difficult I find them as we do more complex things with them. | ||
| + | Readability: | ||
| + | Interesting: | ||
