Tarjan algorithm for the determination of a minimal spanning tree

The algorithm of Tarjan , in the graph theory used to a minimum spanning tree to determine in an undirected connected graphs.

It is a greedy algorithm which in each step selects exactly one edge of the graph either for the minimal spanning tree (colored green) or discarded (colored red). This happens according to two marking rules:

Green rule

Choose a pattern that has at least one uncolored edge that is not yet green. Color the shortest among the uncolored edges of the cut green.

Red rule

Choose a simple circle that has no red and at least one uncolored edge. Color the longest among the uncolored edges in the circle red.

Robert Tarjan has shown that if these rules are observed in a graph, there is always a minimal spanning tree that contains all green, but no red edges. In addition, (at least) one of the two rules is always applicable as long as not all edges of the graph are colored red or green. In the end, the green edges form the minimal spanning tree sought.

For an executable algorithm, the order in which the two rules are used must be specifically defined. This leads, for example, to Kruskal's algorithm or to Prim's algorithm . Both are special cases of Tarjan's algorithm. With the Prim algorithm, only the green rule is systematically applied until a spanning tree is found.

See also

• Tarjan's algorithm for determining strongly connected components
• Hopcroft and Tarjan's algorithm

literature

• Dorothea Wagner: Spanning trees of minimal weight. (Chapter 10, pp. 173-183) In: Thomas Ottmann (Ed.): Principles of the algorithm design. Spectrum Academic Publishing House Heidelberg, Berlin 1998. ISBN 3-8274-0238-7 .