0.7 Graphs  (Page 5/21)

The algorithm begins by examining each vertex and adding the cheapest edge from that vertex to another in the graph, without regard to already added edges, and continues joining these groupings in a like manner until a tree spanning all vertices is completed. Designating each vertex or set of connected vertices a "component", pseudocode for Borůvka's algorithm is:

• Begin with a connected graph G containing edges of distinct weights, and an empty set of edges T
• While the vertices of G connected by T are disjoint:
  • Begin with an empty set of edges E
  • For each component:
    • Begin with an empty set of edges S
    • For each vertex in the component:
      • Add the cheapest edge from the vertex in the component to another vertex in a disjoint component to S
    • Add the cheapest edge in S to E
  • Add the resulting set of edges E to T.
• The resulting set of edges T is the minimum spanning tree of G

Borůvka's algorithm can be shown to run in time O(Elog V), where E is the number of edges, and V is the number of vertices in G.

Other algorithms for this problem include Prim's algorithm (actually discovered by Vojtěch Jarník) and Kruskal's algorithm. Faster algorithms can be obtained by combining Prim's algorithm with Borůvka's. A faster randomized version of Borůvka's algorithm due to Karger, Klein, and Tarjan runs in expected O(E) time. The best known (deterministic) minimum spanning tree algorithm by Bernard Chazelle is based on Borůvka's and runs in O(E α(V)) time, where α is the inverse of the Ackermann function.

7.2.2. kruskal’s algorithms

(From Wikipedia, the free encyclopedia)

Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component). Kruskal's algorithm is an example of a greedy algorithm.

It works as follows:

• create a forest F (a set of trees), where each vertex in the graph is a separate tree
• create a set S containing all the edges in the graph
• while S is nonempty
  • remove an edge with minimum weight from S
  • if that edge connects two different trees, then add it to the forest, combining two trees into a single tree
  • otherwise discard that edge

At the termination of the algorithm, the forest has only one component and forms a minimum spanning tree of the graph.

This algorithm first appeared in Proceedings of the American Mathematical Society, pp. 48–50 in 1956, and was written by Joseph Kruskal.

Performance

Where E is the number of edges in the graph and V is the number of vertices, Kruskal's algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time, all with simple data structures. These running times are equivalent because:

• E is at most V2 and logV2 = 2logV is O(log V).
• If we ignore isolated vertices, which will each be their own component of the minimum spanning tree anyway, V ≤ 2E, so log V is O(log E).