Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:nasona:chapter3 [2018/02/04 17:25] – [3.5 Connectivity in Directed Graphs] nasona | courses:cs211:winter2018:journals:nasona:chapter3 [2018/02/06 15:19] (current) – [3.2 Graph Connectivity and Traversal] nasona | ||
|---|---|---|---|
| Line 107: | Line 107: | ||
| * If there is no path between s and t, then there cannot be a node v that is in the connected component of each. | * If there is no path between s and t, then there cannot be a node v that is in the connected component of each. | ||
| * A natural algorithm for producing all the connected components of a graph, by growing them one component at a time. We start with an arbitrary node s, and use BFS or DFS to generate its connected component. | * A natural algorithm for producing all the connected components of a graph, by growing them one component at a time. We start with an arbitrary node s, and use BFS or DFS to generate its connected component. | ||
| - | |||
| - | |||
| - | ==Questions== | ||
| ==Additional Information== | ==Additional Information== | ||
| Line 196: | Line 193: | ||
| * BFS and DFS spend work only on edges and nodes in the connected component containing the starting node. They never see any of the other, disjointed nodes or edges. | * BFS and DFS spend work only on edges and nodes in the connected component containing the starting node. They never see any of the other, disjointed nodes or edges. | ||
| * The algorithm only spends a constant amount of work on a given edge or node in the iteration when the connected component it belongs to is under consideration. The total runtime is O(n + m). | * The algorithm only spends a constant amount of work on a given edge or node in the iteration when the connected component it belongs to is under consideration. The total runtime is O(n + m). | ||
| - | |||
| - | ==Questions== | ||
| ==Additional Information== | ==Additional Information== | ||
| Line 227: | Line 222: | ||
| * There is an edge of G joining two nodes of the same layer. In this case, G contains an odd-length cycle, and so it cannot be bipartite. | * There is an edge of G joining two nodes of the same layer. In this case, G contains an odd-length cycle, and so it cannot be bipartite. | ||
| * Proof: If two nodes x and y in the same layer are joined by an edge, then the cycle through x, y and their lowest common ancestor z has odd length, so the graph cannot be bipartite. | * Proof: If two nodes x and y in the same layer are joined by an edge, then the cycle through x, y and their lowest common ancestor z has odd length, so the graph cannot be bipartite. | ||
| - | |||
| - | ==Questions== | ||
| ==Additional Information== | ==Additional Information== | ||
| Line 265: | Line 258: | ||
| ==Summary== | ==Summary== | ||
| + | A directed graph is acyclic if it has no cycles. A topological ordering of a graph is an ordering of its nodes as v1, v2,… so that i<j for every edge (vi, vj). In other words, all of the edges are pointing forward. All DAGs have topological orderings. The first node in the topological ordering of an directed acyclic graph would need to have no incoming edges. We can implement an algorithm for finding the topological ordering of a DAG in O(m + n) time by keeping track of the active nodes, keeping track of the number of incoming edges for a given node and maintaining a set that has all of the active nodes in the graph with no incoming edges from other active nodes. The active nodes with no active incoming edges are the ones that will be deleted and added to the topological ordering next because there are no tasks that have precedence over that given node. | ||
| ==Notes== | ==Notes== | ||
| Line 293: | Line 287: | ||
| * Each iteration consists of selecting a node v from the set S and deleting it. After deleting v, we go through the nodes w to which v had an edge and subtract one from the number of active incoming edges that we are maintaining for w. If this makes the number of incoming active edges to w drop to zero, we add w to set S. | * Each iteration consists of selecting a node v from the set S and deleting it. After deleting v, we go through the nodes w to which v had an edge and subtract one from the number of active incoming edges that we are maintaining for w. If this makes the number of incoming active edges to w drop to zero, we add w to set S. | ||
| * This way, we keep track of all nodes eligible for deleting at all times and expend constant work per edge. | * This way, we keep track of all nodes eligible for deleting at all times and expend constant work per edge. | ||
| - | |||
| - | ==Questions== | ||
| ==Additional Information== | ==Additional Information== | ||
