Editing Graph search
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 64: | Line 64: | ||
===Components in graphs=== | ===Components in graphs=== | ||
− | |||
The problems of finding connected components in undirected graphs is solved using graph search; we start the search at some vertex, and after running the search, a vertex has its ''visited'' entry true if and only if it is in the same connected component as the starting vertex. This can be used to assign ''all'' vertices connected component IDs, so that two vertices are in the same component (and reachable from each other). (The proof that one pass of graph search will visit all vertices reachable from the starting vertex can be easily executed by induction on the unweighted distance from the starting vertex.) In fact, we can remove the ''visited'' array because we will be able to tell if a vertex has been visited yet by examining its ID number; if it has not been visited yet, then and ID number has not been assigned, and ''vice versa''. Pseudocode: | The problems of finding connected components in undirected graphs is solved using graph search; we start the search at some vertex, and after running the search, a vertex has its ''visited'' entry true if and only if it is in the same connected component as the starting vertex. This can be used to assign ''all'' vertices connected component IDs, so that two vertices are in the same component (and reachable from each other). (The proof that one pass of graph search will visit all vertices reachable from the starting vertex can be easily executed by induction on the unweighted distance from the starting vertex.) In fact, we can remove the ''visited'' array because we will be able to tell if a vertex has been visited yet by examining its ID number; if it has not been visited yet, then and ID number has not been assigned, and ''vice versa''. Pseudocode: | ||
<pre> | <pre> | ||
Line 86: | Line 85: | ||
We iterate through the vertices one at a time. If, for a given vertex, a component ID has not yet been assigned (it is currently -1), then we assign it the first unused non-negative integer and we do a graph search starting from that vertex, assigning this ID number to all vertices reachable from it. After doing the search, we increment the total number of components found so that the next component will be assigned a higher ID number. But if, when we reach a vertex, a component ID has already been assigned, then we skip that vertex. | We iterate through the vertices one at a time. If, for a given vertex, a component ID has not yet been assigned (it is currently -1), then we assign it the first unused non-negative integer and we do a graph search starting from that vertex, assigning this ID number to all vertices reachable from it. After doing the search, we increment the total number of components found so that the next component will be assigned a higher ID number. But if, when we reach a vertex, a component ID has already been assigned, then we skip that vertex. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
The more complex problem of finding [[biconnected component]]s (or finding [[bridge]]s and [[articulation points]]) in an undirected graph can be solved with a depth-first search algorithm. | The more complex problem of finding [[biconnected component]]s (or finding [[bridge]]s and [[articulation points]]) in an undirected graph can be solved with a depth-first search algorithm. | ||
− | |||
For directed graphs, the equivalent of connected components are [[strongly connected component]]s: again, maximal subsets of the vertices such that inside each component any vertex is reachable from any other. The three best-known algorithms for computing these, [[Tarjan's strongly connected components algorithm|Tarjan's algorithm]], [[Gabow's algorithm]], and [[Kosaraju's algorithm]], all use depth-first searches. The equivalents of articulation points in directed graphs — [[Dominator tree|dominators]] — are computed using depth-first search too. | For directed graphs, the equivalent of connected components are [[strongly connected component]]s: again, maximal subsets of the vertices such that inside each component any vertex is reachable from any other. The three best-known algorithms for computing these, [[Tarjan's strongly connected components algorithm|Tarjan's algorithm]], [[Gabow's algorithm]], and [[Kosaraju's algorithm]], all use depth-first searches. The equivalents of articulation points in directed graphs — [[Dominator tree|dominators]] — are computed using depth-first search too. | ||