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:35] – [3.3 Implementing Graph Traversal Using Queues and Stacks] patelk | courses:cs211:winter2018:journals:patelk:chapter3 [2018/02/05 05:40] (current) – [3.6 Directed Acyclic Graphs and Topological Ordering] patelk | ||
|---|---|---|---|
| Line 169: | Line 169: | ||
| - There is an edge of G joining two nodes of the same layer: Not Bipartite | - There is an edge of G joining two nodes of the same layer: Not Bipartite | ||
| + | ==== Personal Thoughts ==== | ||
| + | I don't really remember bipartite graphs from other classes, but they are pretty simple and this section made them very simple. We did already talk about them in class, so that did help as well. There wasn't any information that was too confusing in this short section. | ||
| + | Readability: | ||
| + | Interesting: | ||
| ===== 3.5 Connectivity in Directed Graphs===== | ===== 3.5 Connectivity in Directed Graphs===== | ||
| Line 197: | 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 214: | 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 230: | 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: | ||
