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 03:01] – [3.2 - Graph Connectivity and Graph Traversal] margoliesd | courses:cs211:winter2011:journals:david:chapter3 [2011/02/15 01:12] (current) – [3.6 - Directed Acyclic Graphs and Topological Ordering] margoliesd |
|---|
| A path in an undirected graph is the sequence of nodes needed to get from one node to another. A "simple" path does not repeat any nodes, while a "cycle" ends where it began. A path in a directed graph is similar to a path in an undirected graph: we just need to make sure that we keep the directionality of the edges in mind. A "connected" undirected graph occurs when there is a path from every node to every other node. A "strongly connected" directed graph occurs when there is a path from every node to every other node, keeping in mind that the path must respect the directionality of the edges. The "distance" between any two nodes is the shortest path required to get from one node to the other. An "tree" is an undirected graph with no cycles. This allows us to represent a hierarchy. | A path in an undirected graph is the sequence of nodes needed to get from one node to another. A "simple" path does not repeat any nodes, while a "cycle" ends where it began. A path in a directed graph is similar to a path in an undirected graph: we just need to make sure that we keep the directionality of the edges in mind. A "connected" undirected graph occurs when there is a path from every node to every other node. A "strongly connected" directed graph occurs when there is a path from every node to every other node, keeping in mind that the path must respect the directionality of the edges. The "distance" between any two nodes is the shortest path required to get from one node to the other. An "tree" is an undirected graph with no cycles. This allows us to represent a hierarchy. |
| |
| | Readability: 7/10 |
| ====3.2 - Graph Connectivity and Graph Traversal==== | ====3.2 - Graph Connectivity and Graph Traversal==== |
| The //s-t connectivity// problem asks if there is a path from node //s// to node //t//. Two algorithms for answering this problem are breadth-first search and depth-first search. Breadth first search puts node //s// in the first layer, and every node that has an edge with //s// goes in the second layer. Every new node that has an edge with a node in the second layer goes in the third layer, and this continues until no new nodes are found. The distance between nodes //s// and //t// is how many layers away they are. Breadth first search also gives us a tree rooted at //s//. Any nodes in the tree that have edges but are not in a parent-child relationship are at most one layer way. We can call all the nodes in these layers a connected component. | The //s-t connectivity// problem asks if there is a path from node //s// to node //t//. Two algorithms for answering this problem are breadth-first search and depth-first search. Breadth first search puts node //s// in the first layer, and every node that has an edge with //s// goes in the second layer. Every new node that has an edge with a node in the second layer goes in the third layer, and this continues until no new nodes are found. The distance between nodes //s// and //t// is how many layers away they are. Breadth first search also gives us a tree rooted at //s//. Any nodes in the tree that have edges but are not in a parent-child relationship are at most one layer way. We can call all the nodes in these layers a connected component. |
| Readability: 6/10 | Readability: 6/10 |
| |
| | ====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: 7/10 |
