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/06 15:19] – [3.4 Bipartite Graphs: An Application of BFS] 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== | ||
