Differences

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

--- courses:cs211:winter2018:journals:cohene:home:chapter3 [2018/02/07 00:30] – [3.4: Testing Bipartiteness: An Application of Breadth-First Search] cohene
+++ courses:cs211:winter2018:journals:cohene:home:chapter3 [2018/02/07 00:55] (current) – [3.6: Directed Acyclic Graphs and Topological Ordering] cohene
@@ Line 34: / Line 34: @@
 We can test for bipartitness by doing the following: first, assume that the graph, G, is connected. Then, pick any node s∈V and color it red. All of its neighbors are then colored blue. Next, all of the neighbors of those nodes are colored red, until the entire graph has been colored. This allows us to visualize whether or not we have a bipartite graph. This description is the same as the process for BFS. Just like BFS, the runtime for the coloring algorithm is O(n+m).
 ===== 3.5: Connectivity in Directed Graphs=====
+This section tackles the issue of directed graphs. To represent directed graphs, we will still use an adjacency list. Instead of each node having a single list of neighbors, each node has two lists- one for nodes to which it has edges and one to which it has edges from. BFS and DFS are very similar to how they are in undirected graphs. To use BFS as an example, first we start at a node s. Then we define a layer of nodes to conist of all those to which s has an edge, and a second layer for the additional nodes to which these first-layer nodes have edges. This way nodes are discovered in each layer in an outward search from s and we get the shortest path from s with j edges (j being the layer). This results in a running time of O(m+n). DFS still runs in linear time and results in the same set of nodes. It runs the same except DFS can only travel in the direction of the edges.
+A graph is strongly connected if, for two nodes u and v, u and v have a path as well as v and u. u and v are mutually reachable if it is strongly connected. There are several properties that can be derived from this. First, if u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable. We can check in linear time if a directed graph is strongly connected. We can define the strong component containing a node s in a directed graph to be the set of all v such that s and v are mutually reachable. Furthermore, for any two nodes s and t in a directed graph, their strong components are either identical or disjoint.
 ===== 3.6: Directed Acyclic Graphs and Topological Ordering=====
+If a directed graph has no cycles it is considered a directed acyclic graph (DAG). DAGs can be used for precedence relations or dependencies. Given a set of tasks with dependencies, it is natural to look for an order in which the tasks should be performed. This looks for topological ordering, where all edges point forward in the ordering.
+We look here to check if every DAG has a topological ordering. To do so, we need to find which node goes at the beginning of a topological ordering. In every DAG there must be a node with no incoming edges, which will be the starting node. This will help us build our topological ordering. Once we remove the starting node, we must find the next node with no incoming edges. If we repeat this pattern, we will eventually build our order. This section int he textbook really helps to clarify our discussion of this topic in class. In this algorithm, finding a node v with no incoming edges and deleting it will be done in O(n), and the algorithm itself runs n times, so the total running time is O(n^2). By iteratively deleting nodes with no incoming edges we can achieve a running time of O(m+n).