Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:donohuem:chapter3 [2018/02/07 01:40] – donohuem
+++ courses:cs211:winter2018:journals:donohuem:chapter3 [2018/02/07 02:17] (current) – donohuem
@@ Line 12: / Line 12: @@
-===== 3.4 Testing Bipartiteness: An application of Breadth-First Search =====
+===== 3.4 Testing Bipartiteness: An Application of BFS =====
 A bipartite graph is one where its nodes can be separated into sets of either "red" or "blue" nodes such that every edge has a red and blue end. A bipartite graph cannot contain an odd cycle. So, an algorithm that tests for bipartiteness of graphs need only check for odd cycles. This test for bipartiteness algorithm is essentially BFS with the additional step of coloring each layer of nodes and checking whether there is any edge has two ends of the same color. Thus, the run time of this algorithm is O(m + n). Overall, the readability was 7/10.
+===== 3.5 Connectivity in Directed Graphs =====
+When representing directed graphs, we use a modified version of the adjacency list. The search algorithms (BFS and DFS) for undirected graphs are almost the same for directed graphs with slight exceptions. For example, a BFS on nodes and s and t may reveal that a path exists between from s to t AND from t to s. For a directed graph, however, it is not a guarantee that t may have a path to s. An important notion is this section is Strong Connectivity. A graph is strongly connected if every two nodes are mutually reachable -- a path exists from nodes s to t and t to s. An algorithm to test whether a directed graph is strongly connected can be done in linear time. Overall, the readability of this section was 7/10.
+===== 3.6 Directed Acyclic Graphs and Topological Ordering =====
+A DAG is simply a directed graph that has no cycles. DAGs are common structures in computer science. A relatable example is a graph showing prerequisite course requirements for a major, with each node representing a course. If a graph is a DAG, then it must have a topological ordering. A topological ordering is a organization of a graph such that all edges point from left to right. We can use an algorithm that computes a topological ordering for a DAG. First we must find a node with no incoming edges, order it first, then delete it from the graph. We then recursively call the algorithm. The run time for this algorithm is ostensibly O(n^2) because finding a node with no incoming edges takes O(n) time in addition to recursively running the algorithm for n iterations. However, we can reduce this run time to O(m + n) by more efficiently finding a node with no incoming edges. Overall, the readability of this section was 6/10.