Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:boyese:chapter3 [2018/02/07 00:47] – [Section 3.4: Testing Bipartiteness: An Application of Breadth-First Search] boyese | courses:cs211:winter2018:journals:boyese:chapter3 [2018/02/07 00:51] (current) – [Section 3.6: Directed Acyclic Graphs and Topological Ordering] boyese | ||
|---|---|---|---|
| Line 226: | Line 226: | ||
| **Theorem 3.17** //For any two nodes s and t in a directed graph, their strong components are either identical or disjoint.// | **Theorem 3.17** //For any two nodes s and t in a directed graph, their strong components are either identical or disjoint.// | ||
| + | |||
| + | The idea of this section was relatively simple and I think the explanation was too long winded for the simplicity of the idea. I am also wondering how connected graphs can be used differently than non-connected graphs and what their purpose is in computer science. This section was short and to the point so I would give it an 8/10 for readability. | ||
| =====Section 3.6: Directed Acyclic Graphs and Topological Ordering===== | =====Section 3.6: Directed Acyclic Graphs and Topological Ordering===== | ||
| Line 256: | Line 258: | ||
| To bound the running time of this algorithm, we note that identifying a node v with no incoming edges, and deleting it from G, can be done in O(n) time. Since the algorithm runs for n iterations, the total running time is O(n< | To bound the running time of this algorithm, we note that identifying a node v with no incoming edges, and deleting it from G, can be done in O(n) time. Since the algorithm runs for n iterations, the total running time is O(n< | ||
| + | |||
| + | I thought this section was interesting because of it's applications in the real world and in programming. I would give this section a 9/10 for readability because it was short and to the point. | ||
