Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:cantrella:chapter_3 [2018/02/06 19:05] – [Section 3.4] cantrella | courses:cs211:winter2018:journals:cantrella:chapter_3 [2018/02/06 22:20] (current) – [Section 3.6] cantrella | ||
|---|---|---|---|
| Line 27: | Line 27: | ||
| This section helped give me a greater of bipartite graphs and how we determine them, I give this section a 7 on readability and a 7 on the interesting scale. | This section helped give me a greater of bipartite graphs and how we determine them, I give this section a 7 on readability and a 7 on the interesting scale. | ||
| ===== Section 3.5 ===== | ===== Section 3.5 ===== | ||
| + | After discussing in detail the connectivity possibilities in undirected (or doubly-directed) graphs, section 3.5 turns our attention to directed graphs. This means each edge point in a direction which has interesting implication for the connectivity of the graph. As it turns out, neither the BFS nor DFS algorithm change too much when directed graphs come into play. The algorithms can be used the set of nodes G which some node //u// is pointing to or the set of nodes Grev which is a list of nodes that point at node //u//. Running either a BFS or DFS on both incoming and outgoing nodes can be used to show that a graph has strong connectivity. That is, every connection between node //u// and //v// goes both ways. This means the graph, while directed, can essentially be treated like an undirected graph. | ||
| + | |||
| + | 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. | ||
