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 18:59] – [Section 3.3] cantrella | courses:cs211:winter2018:journals:cantrella:chapter_3 [2018/02/06 22:20] (current) – [Section 3.6] cantrella | ||
|---|---|---|---|
| Line 23: | Line 23: | ||
| This was an interesting chapter, I give it an 8 on the interesting scale and a 6 on the readability scale. The runtime for both algorithms was O(//m// + //n//). | This was an interesting chapter, I give it an 8 on the interesting scale and a 6 on the readability scale. The runtime for both algorithms was O(//m// + //n//). | ||
| ===== Section 3.4 ===== | ===== Section 3.4 ===== | ||
| + | Section 3.4 demonstrates the usefulness of BFS with a demonstration of BFS can be used to show bipartiteness in graphs. Using the same algorithm we used before to generate a bread-first search layering of the graph, we add two constant actions of coloring the node blue if is in an odd layer and even if it is in an even layer. Adding the two constant actions does not increase run-time, so the algorithm runs in O(//n// + //m//) time. In addition, if there are no odd-length cycles in the graph, we will know for sure that we have a bipartite graph. | ||
| + | |||
| + | 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. | ||
