Mathematical
Programming
 		Kruskal's Algorithm

Simplex

Twophase

Dijkstra

Prim

Kruskal

Ford-Fulkerson

Kruskal
Java applet demos:
FAQ
Japanese/English

MST Problem:

Given a connected graph G=(V,E) and a weight d:E->R+, find a minimum spanning tree T.

Kruskal's Algorithm

  1. Set i=1 and let E0={}
  2. Select an edge ei of minimum value not in Ei-1 such that Ti=<Ei-1 cup {ei} >is acyclic and define Ei=Ei-1 cup {ei}. If no such edge exists, Let T=<Ei>and stop.
  3. Replace i by i+1. Return to Step 2.
The time required by Kruskal's algorithm is O(|E|log|V|).

Java Source Files:

Java Applet Demos

See Also

Kenji Ikeda's
Home Page		 Last Modified: Wednesday, 07-Jun-2000 16:26:48 JST