Here the white nodes are those whose distance field is ∞, the gray nodes are those We can compute distances explicitly by replacing the colors with a distance field: The BFS pseudo-code looks like this:īreadth-first search is so called because it explores nodes in the order of their distance from the root, where distance is defined as the minimum path length from a root to the node. The two most common graph traversal algorithms are breadth-first search (BFS) and depth-first search (DFS). The invariantĮnsures that whatever graph traversal we choose, the algorithm will work even when That the tricolor algorithm works even when gray nodes are processedĬoncurrently, as long as the black-white invariant is maintained. One advantage of defining graph search in terms of the tricolor algorithm is Moreover,īecause the black-white invariant is maintained, it must reach all reachable nodes in the graph. However, as long as it does some work on each gray node that it picks,Īny implementation that can be described in terms of this algorithm will finish. That such an algorithm is nondeterministic because its next step is not uniquelyĭefined. It allows the particular implementation to choose the node n fromĪmong the gray nodes it allows choosing which and how many white successors toĬolor gray and it allows delaying the coloring of gray nodes black. This algorithm is abstract enough to describe many different graph if n has no white successors, optionally color n black.Color the root node gray and all other nodes white.True at the end, we know that any remaining white nodes cannot be reached from This is clearly true initially, and because it is There is no edge from a black node to a white node. The algorithm maintains a key black-white invariant at all times:Ģ. Initially there are no black nodes and the root is gray.Īs the algorithm progresses, white nodes turn into gray nodes and gray nodes turn into black nodes.Įventually there are no gray nodes left and the algorithm is done. The progress of the algorithm is depicted by the following figure. These nodes are on the frontier between white and black. Gray nodes are nodes that have been discovered but that the algorithm is still processing.Black nodes are reachable nodes that the algorithm has already visited and is finished processing.White nodes are undiscovered nodes that have not been seen yet in the current traversal and may even be unreachable.In this algorithm, graph nodes areĪssigned one of three colors that can change over time: Tricolor algorithmĪbstractly, graph traversal can be expressed in terms of the tricolorĪlgorithm due to Dijkstra and others. In an undirected graph we follow all edges inĪ directed graph we follow only out-edges. Generally, the goal of a graph traversal is to visit all nodes reachableįrom a given root node or set of root nodes. Determining whether a graph is a dag (directed acyclic graph).Finding the best path through a graph (e.g., routing and map directions).The minmax best reachable node (e.g., two-player game search) Finding the best reachable node (e.g., single-player game search) or.Finding all reachable nodes (e.g., for garbage collection).We often want to solve problems that are expressible in terms of a traversal or search over a graph.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |