Differences

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

--- courses:cs211:winter2018:journals:mccaffreyk:home:3 [2018/02/06 04:21] – [Section 3.3: Implementing Graph Traversal Using Queues and Stacks] mccaffreyk
+++ courses:cs211:winter2018:journals:mccaffreyk:home:3 [2018/02/06 05:00] (current) – [Section 3.6: Directed Acyclic Graphs and Topological Ordering] mccaffreyk
@@ Line 12: / Line 12: @@
 ==== Section 3.3: Implementing Graph Traversal Using Queues and Stacks ====
-We use adjacency lists to represent graphs. We will treat nodes as n and edges as m, and compute run-time in terms of both n and m. We cannot say for sure if n or m is more significant, so we will treat them as equals. However, m<= n^2 always. For both breadth and depth search, we aim for O(n+m) time. An alternative representation is the adjacency matrix(constant access, O(n^2) space. Adjacency list: array of nodes with corresponding linked lists of connected edges for each node. Just O(n+m) space rather than O(n^2). Since the order of nodes is crucial, queues and stacks are ideal data structures to represent them. In BFS, nodes are organized using a queue while in DFS, nodes are organized using a stack(recursive). Finding the set of all connected components is still O(n+m) for both techniques.
+We use adjacency lists to represent graphs. We will treat nodes as n and edges as m, and compute run-time in terms of both n and m. We cannot say for sure if n or m is more significant, so we will treat them as equals. However, m<= n^2 always. For both breadth and depth search, we aim for O(n+m) time. An alternative representation is the adjacency matrix(constant access, O(n^2) space. Adjacency list: array of nodes with corresponding linked lists of connected edges for each node. Just O(n+m) space rather than O(n^2). Since the order of nodes is crucial, queues and stacks are ideal data structures to represent them. In BFS, nodes are organized using a queue while in DFS, nodes are organized using a stack(recursive). Finding the set of all connected components is still O(n+m) for both techniques. This section was harder to follow: 6.5/10.
+==== Section 3.4: Testing Bipartiteness: An Application of Depth First Search ====
+Bipartite Graphs cannot have nodes in the same layer connect-> strategy: color each layer red or blue and if any edge has the same color on both ends the graph is not bipartite. These are "forward graphs". If a graph is bipartite then it cannot contain an odd cycle. Algorithm: perform breadth first search to add colors. Then, after this step, scan through the resulting tree to see if condition is met. Unsurprisingly, the total running time of this algorithm is O(n+m).
+==== Section 3.5: Connectivity in Directed Graphs ====
+Directed graphs are one directional: edges must go from node a to node b and cannot go back from node b to node a. We still use adjacency lists for directed graphs but maintain two lists of edges: a to list and a from list. Searching is basically the same(time, techniques, etc) as in non-directed graphs, but must only follow nodes according to inherent direction. If a directed graph is strongly connected, every pair of nodes a and b must have paths between them (path from a to b and from b to a). Not always the case here. This has transitive properties: if a and b are mutually reachable, nodes b and c are mutually reachable, a and c must also be mutually reachable. This allows us to conclude that "strong components" of graphs are either identical or completely different(disjoint).
+==== Section 3.6: Directed Acyclic Graphs and Topological Ordering ====
+A directed acyclic graph is a directed graph with no cycles. The structure of these is often much richer than non-directed graphs without cycles(more edges). These DAGS are naturally ordered and usually applied to systems such as college courses where one cannot backtrack directly. The comparative classification of nodes in a DAG is called a "topological ordering". In a topological ordering, all edges must "point forward". If a graph has a topological ordering than it is a DAG. Further, is a graph is a DAG than it must have a topological ordering. The lowest node of any DAG has no incoming edges. There can also be other nodes with no incoming edges. Computing a topological ordering for a DAG takes O(n^2) time but may take O(n+m) only for very thin, non-dense graphs.