Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
courses:cs211:winter2011:journals:david:chapter3 [2011/02/02 02:31] โ margoliesd | courses:cs211:winter2011:journals:david:chapter3 [2011/02/15 01:12] (current) โ [3.6 - Directed Acyclic Graphs and Topological Ordering] margoliesd | ||
---|---|---|---|
Line 5: | Line 5: | ||
A path in an undirected graph is the sequence of nodes needed to get from one node to another. A " | A path in an undirected graph is the sequence of nodes needed to get from one node to another. A " | ||
+ | Readability: | ||
====3.2 - Graph Connectivity and Graph Traversal==== | ====3.2 - Graph Connectivity and Graph Traversal==== | ||
The //s-t connectivity// | The //s-t connectivity// | ||
Line 10: | Line 11: | ||
Depth-First search follows edges from //s// until it reaches a dead end. It then backtracks to a node with an unexplored edge and continues on that path until it reaches a dead end at which point it backtracks again. If we eventually get to //t// then we know there is a path from //s// to // | Depth-First search follows edges from //s// until it reaches a dead end. It then backtracks to a node with an unexplored edge and continues on that path until it reaches a dead end at which point it backtracks again. If we eventually get to //t// then we know there is a path from //s// to // | ||
+ | Readability: | ||
====3.3 - Implementing Graph Traversal Using Queues and Stacks==== | ====3.3 - Implementing Graph Traversal Using Queues and Stacks==== | ||
A graph can either be represented with an adjacency matrix or an adjacency list. For more sparsely linked graphs, an adjacency list makes sense because we often need to look at all nodes connected to a particular node. While this is O(n) for both the matrix and the list, if a we assume a sparsely linked graph, the list requires less actual steps. Because both Breadth First Search and Depth First Search need to process a set of elements, we can maintain these elements in a linked list. We can use the linked list as a either a queue (first in first out) or a stack (last in first out). For Breadth First Search, we can have an array that tells if a node has already been seen or " | A graph can either be represented with an adjacency matrix or an adjacency list. For more sparsely linked graphs, an adjacency list makes sense because we often need to look at all nodes connected to a particular node. While this is O(n) for both the matrix and the list, if a we assume a sparsely linked graph, the list requires less actual steps. Because both Breadth First Search and Depth First Search need to process a set of elements, we can maintain these elements in a linked list. We can use the linked list as a either a queue (first in first out) or a stack (last in first out). For Breadth First Search, we can have an array that tells if a node has already been seen or " | ||
+ | |||
+ | Readability: | ||
====3.4 - Testing Bipartiteness: | ====3.4 - Testing Bipartiteness: | ||
+ | |||
+ | A bipartite graph is one in which the set of nodes can be partitioned into two sets such that every edge has a node in one set and a node in the other. If a graph is bipartite, then it has no odd length cycles. To test for bipartiteness, | ||
+ | |||
+ | Readability: | ||
+ | ====3.5 - Connectivity in Directed Graphs==== | ||
+ | To represent a directed graph, we give each node two lists of neighbors. One list contains the nodes //to// which it has edges and one the nodes //from// which it has edges. Breadth First Search is similar to the undirected graph, but it only tells us if there is a path from the seed node to another found node, and not the other way around. To accomplish the opposite, we can reverse every edge and perform the algorithm again. Depth first search also works similar to the case for an undirected graph. If there is a path from one node to another, and also a path back, then the nodes are considered mutually reachable. If all nodes are mutually reachable, the directed graph is strongly connected. If nodes //a// and //b// are mutually reachable and nodes //b// and //c// are mutually reachable, then nodes //a// and //c// are mutually reachable as well. | ||
+ | |||
+ | Readability: | ||
+ | |||
+ | ====3.6 - Directed Acyclic Graphs and Topological Ordering==== | ||
+ | |||
+ | A directed graph with no cycles is called a Directed Acyclic Graph. We can use a DAG to represent dependencies or precedence relationships. A topological ordering of a DAG is an ordering of nodes in which each edge points forward along the list. Therefore, the first node must have no edge pointing to it. Some facts about DAG's: if a graph has a topological ordering, then it is a DAG, and if a graph is a DAG, then it must have a topological ordering. The compute the topological ordering of a DAG, we find a node with no incoming edges, delete it from the graph, and add it to the topological ordering. We recursively find nodes with no incoming edges, and add each of those to the topological ordering in the order they were found. We can achieve a running time of O(n+m) for this algorithm if we also keep track of nodes that have not yet been deleted (active nodes). For each node, we keep track of the number of incoming edges that it has from active nodes, and we keep track of all the active nodes that do not share an edge with an active node. This way, we can subtract the number of edges from each node incident to the one deleted, which makes it faster to find the next node with no incoming edges. | ||
+ | |||
+ | Readability: |