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:44] – [Section 3.3: Implementing Graph Traversal Using Queues and Stacks] boyese | courses:cs211:winter2018:journals:boyese:chapter3 [2018/02/07 00:51] (current) – [Section 3.6: Directed Acyclic Graphs and Topological Ordering] boyese | ||
|---|---|---|---|
| Line 204: | Line 204: | ||
| (ii) There is an edge of G joining two nodes of the same layer. In this case, G contains an odd-length cycle, and so it cannot be bipartite.// | (ii) There is an edge of G joining two nodes of the same layer. In this case, G contains an odd-length cycle, and so it cannot be bipartite.// | ||
| + | I'm still a bit unsure of what being bipartite means and why it's important. I think testing a graph for bipartiteness as a homework exercise would help me to understand better how the algorithm works. I also am not sure what the applications of knowing whether a graph is bipartite or not are, or if the point of introducing it in this chapter is another way of showing how BFS can be used. I would give this section a 6/10 for readability because I think it was very technical. | ||
| =====Section 3.5: Connectivity in Directed Graphs===== | =====Section 3.5: Connectivity in Directed Graphs===== | ||
| 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. | ||
