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:35] – [3.6 Directed Acyclic Graphs and Topological Ordering] 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 294: | 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== | ||
