Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:cantrella:chapter_3 [2018/02/06 19:28] – [Section 3.5] cantrella | courses:cs211:winter2018:journals:cantrella:chapter_3 [2018/02/06 22:20] (current) – [Section 3.6] cantrella | ||
|---|---|---|---|
| Line 31: | Line 31: | ||
| The representation of the new adjacency list that included two linked lists for each node, one for incoming and one for outgoing edges, was interesting as I did not totally understand it in class. I give this section an 8 on the interesting scale a 9 for readability. | The representation of the new adjacency list that included two linked lists for each node, one for incoming and one for outgoing edges, was interesting as I did not totally understand it in class. I give this section an 8 on the interesting scale a 9 for readability. | ||
| ===== Section 3.6 ===== | ===== Section 3.6 ===== | ||
| + | Section 3.6 introduces the concept of a Directed Acyclic Graph, shows some of the basic logic behind them, and gives us an algorithm that can determine if some graph has a DAG. The chapter first defines a DAG, then shows that if some graph G has a topological ordering is automatically a DAG, and vice versa. Then, the book introduces an algorithm for the topological ordering in some directed graph by finding a node with no incoming edges, adding it to the ordering and deleting it from the graph, and then recursively calling the algorithm to look at the rest of the graph. This algorithm, unfortunately, | ||
| + | I give this chapter a 9 on the interesting scale and a 7 for readability. | ||
