Difference between revisions of "Kruskal's algorithm"

From Wiki @ Karl Jones dot com
Jump to: navigation, search
Line 5: Line 5:
 
The algorithm finds an edge of the least possible weight that connects any two trees in the forest.
 
The algorithm finds an edge of the least possible weight that connects any two trees in the forest.
  
It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.
+
It is a greedy algorithm in [[graph theory]] as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.
  
 
* 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.
 
* 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.
Line 14: Line 14:
  
 
* [[Algorithm]]
 
* [[Algorithm]]
 +
* [[Graph theory]]
 
* [[Maze generation algorithm]]
 
* [[Maze generation algorithm]]
  

Revision as of 06:28, 8 February 2016

Kruskal's algorithm is a minimum-spanning-tree algorithm.

Description

The algorithm finds an edge of the least possible weight that connects any two trees in the forest.

It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

  • 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).

See also

External links