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 1: | Line 1: | ||
− | In [[graph theory]], '''graph search''' or '''graph traversal''' refers to the technique of "visiting" each vertex of the graph in turn, executing some code whenever a vertex is "visited". By varying the order in which vertices are visited and the nature of the action performed when a vertex is visited, many interesting problems in graph theory can be solved efficiently. Conversely, many graph-theoretic algorithms can be classified as graph search algorithms | + | In [[graph theory]], '''graph search''' or '''graph traversal''' refers to the technique of "visiting" each vertex of the graph in turn, executing some code whenever a vertex is "visited". By varying the order in which vertices are visited and the nature of the action performed when a vertex is visited, many interesting problems in graph theory can be solved efficiently. Conversely, many graph-theoretic algorithms can be classified as graph search algorithms: [[Dijkstra's algorithm]], [[Prim's algorithm]], [[A*]], [[topological sorting]], the algorithms to find [[bridge]]s and [[articulation point]]s, the [[strongly connected component]]-finding algorithms of [[Tarjan's strongly connected components algorithm|Tarjan]], [[Kosaraju's algorithm|Kosaraju]], and [[Gabow's algorithm|Gabow]], and the augmenting path techniques ([[Ford-Fulkerson method]] and [[Dinic's algorithm]]) for the [[maximum flow]] problem all depend upon graph search. |
− | + | =Basic principles of graph search= | |
Although theoretically one can visit the vertices of a graph in any order, in all useful graph search algorithms the choice of which vertex to visit next is taken from the immediate neighbours of vertices that have already been visited. (Obviously, the first vertex visited does not follow this rule.) This means that usually the algorithm must be invoked separately on each [[connected component]] of the graph, because it is impossible to visit a vertex if the algorithm starts in a different component. The set of all vertices which have not yet been visited but may be visited next (because they are immediate neighbours of already-visited vertices) is called the ''fringe''. | Although theoretically one can visit the vertices of a graph in any order, in all useful graph search algorithms the choice of which vertex to visit next is taken from the immediate neighbours of vertices that have already been visited. (Obviously, the first vertex visited does not follow this rule.) This means that usually the algorithm must be invoked separately on each [[connected component]] of the graph, because it is impossible to visit a vertex if the algorithm starts in a different component. The set of all vertices which have not yet been visited but may be visited next (because they are immediate neighbours of already-visited vertices) is called the ''fringe''. | ||
− | + | =Pseudocode for generic graph search algorithm= | |
<pre> | <pre> | ||
input G | input G | ||
for each connected component C ∈ G | for each connected component C ∈ G | ||
− | for | + | for all v ∈ V(C) |
let visited[v] = false | let visited[v] = false | ||
let u = some vertex ∈ V(C) | let u = some vertex ∈ V(C) | ||
Line 21: | Line 21: | ||
add v to F | add v to F | ||
</pre> | </pre> | ||
+ | Some of the notation used is explained at [[PEGWiki:Pseudocode conventions]].<br/> | ||
Here is a line-by-line analysis of the code: | Here is a line-by-line analysis of the code: | ||
* We run the graph search exactly once for each connected component in the graph (''for each connected component C ∈ G''). | * We run the graph search exactly once for each connected component in the graph (''for each connected component C ∈ G''). | ||
Line 28: | Line 29: | ||
* When the fringe is not empty, we select any vertex in ''F'' (''u = some vertex ∈ F'') and remove it from ''F''. If ''u'' has already been visited, we have nothing more to do for ''u''. Otherwise (''if visited[u] = false''), we "visit" ''u'', whatever "visit" happens to mean in the particular algorithm we are using. We record that ''u'' has been visited (''visited[u] = true''). | * When the fringe is not empty, we select any vertex in ''F'' (''u = some vertex ∈ F'') and remove it from ''F''. If ''u'' has already been visited, we have nothing more to do for ''u''. Otherwise (''if visited[u] = false''), we "visit" ''u'', whatever "visit" happens to mean in the particular algorithm we are using. We record that ''u'' has been visited (''visited[u] = true''). | ||
* After visiting ''u'', we add any neighbours of ''u'' (''for each v ∈ V(C) such that (u,v) ∈ E(G)'') to the fringe ''F'' that have not been visited already (''and visited[v] = false''). Then the loop starts over again, meaning that these newly added vertices are eventually visited. | * After visiting ''u'', we add any neighbours of ''u'' (''for each v ∈ V(C) such that (u,v) ∈ E(G)'') to the fringe ''F'' that have not been visited already (''and visited[v] = false''). Then the loop starts over again, meaning that these newly added vertices are eventually visited. | ||
− | + | <br/> | |
As it stands, this code has a serious flaw: how do we know what the connected components of the graph are? As a matter of fact, breadth-first search and depth-first search are usually used to ''find'' the connected components, but they are themselves graph search! The solution is as follows: if a connected component has already been examined, then all vertices in that component have been visited, or, contrapositively, if a vertex has not been visited, then its component has not been visited either. This allows us to rewrite the code as | As it stands, this code has a serious flaw: how do we know what the connected components of the graph are? As a matter of fact, breadth-first search and depth-first search are usually used to ''find'' the connected components, but they are themselves graph search! The solution is as follows: if a connected component has already been examined, then all vertices in that component have been visited, or, contrapositively, if a vertex has not been visited, then its component has not been visited either. This allows us to rewrite the code as | ||
<pre> | <pre> | ||
input G | input G | ||
− | for | + | for all u ∈ V(G) |
let visited[u] = false | let visited[u] = false | ||
− | for each u ∈ | + | for each vertex u ∈ G |
if visited[u]=false | if visited[u]=false | ||
let F = {u} | let F = {u} | ||
Line 47: | Line 48: | ||
</pre> | </pre> | ||
Notice that ''F'' is not necessarily a real set in the mathematical sense; ''F'' might contain multiple copies of a vertex. The nature of ''F'' is dependent upon what type of graph search algorithm is being used. Also, an actual implementation of graph search need not actually look like this. For example, depth-first search is often implemented [[recursion|recursively]]. However, all graph search algorithms can be made to fit this form.<br/> | Notice that ''F'' is not necessarily a real set in the mathematical sense; ''F'' might contain multiple copies of a vertex. The nature of ''F'' is dependent upon what type of graph search algorithm is being used. Also, an actual implementation of graph search need not actually look like this. For example, depth-first search is often implemented [[recursion|recursively]]. However, all graph search algorithms can be made to fit this form.<br/> | ||
+ | <br/> | ||
− | + | =Types of graph search algorithms= | |
Many details have been left out of the generic code above. For example, we are free to choose the initial vertex ''u'' in any way we want, to iterate over the connected components in any order, and to iterate over the neighbours of ''u'' in any order. However, there are two places where variation is most important: the instruction ''visit u'' can mean practically anything, leading to endless variety in graph algorithms, and selecting the next vertex from ''F'' can be done in various ways. When you learn a new algorithm, try to identify these choices and understand how they are crucial to the correctness of the algorithm. There are three common paradigms for the selection of the next vertex: breadth-first search, depth-first search, and priority-first search. | Many details have been left out of the generic code above. For example, we are free to choose the initial vertex ''u'' in any way we want, to iterate over the connected components in any order, and to iterate over the neighbours of ''u'' in any order. However, there are two places where variation is most important: the instruction ''visit u'' can mean practically anything, leading to endless variety in graph algorithms, and selecting the next vertex from ''F'' can be done in various ways. When you learn a new algorithm, try to identify these choices and understand how they are crucial to the correctness of the algorithm. There are three common paradigms for the selection of the next vertex: breadth-first search, depth-first search, and priority-first search. | ||
− | + | ==Breadth-first search== | |
In [[breadth-first search]], the next vertex selected from ''F'' is always the oldest remaining vertex in ''F'' (the one that was placed into ''F'' first.) That is, ''F'' is a FIFO (first in, first out) [[queue]]. | In [[breadth-first search]], the next vertex selected from ''F'' is always the oldest remaining vertex in ''F'' (the one that was placed into ''F'' first.) That is, ''F'' is a FIFO (first in, first out) [[queue]]. | ||
− | + | ==Depth-first search== | |
In [[depth-first search]], the next vertex selected from ''F'' is always the newest remaining vertex (the one most recently added to ''F''). That is, ''F'' is a LIFO (last-in, first out) [[stack]]. | In [[depth-first search]], the next vertex selected from ''F'' is always the newest remaining vertex (the one most recently added to ''F''). That is, ''F'' is a LIFO (last-in, first out) [[stack]]. | ||
− | + | ==Priority-first search== | |
− | In priority-first search, each vertex is assigned a priority, and whenever a vertex is to be selected from ''F'', the one with the highest priority is selected. This is the basis of | + | In priority-first search, each vertex is assigned a priority, and whenever a vertex is to be selected from ''F'', the one with the highest priority is selected. This is the basis of [[Dijkstra's algorithm]] and [[Prim's algorithm]]. |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + |