HTML (24.65 kB)
Download
Title Details:
Kruskal's algorithm
Other Titles: Application of Algorithm
Authors: Georgiou, Dimitrios
Antoniou, Efstathios
Chatzimichailidis, Anestis
Subject: MATHEMATICS AND COMPUTER SCIENCE > COMPUTER SCIENCE > DISCRETE STRUCTURES > GRAPHS AND TREES
Keywords:
Graphs
Description:
Abstract:
Kruskal's algorithm is a minimum-spanning-tree algorithm which 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.

1. create a forest F (a set of trees), where each vertex in the graph is a separate tree
2. create a set S containing all the edges in the graph
3. while S is nonempty and F is not yet spanning remove an edge with minimum weight from S
4. if the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree

At the termination of the algorithm, the forest forms a minimum spanning forest of the graph. If the graph is connected, the forest has a single component and forms a minimum spanning tree.
Type: Simulation
Creation Date: 2015
Item Details:
License: http://creativecommons.org/licenses/by-nc-nd/3.0/gr
Handle http://hdl.handle.net/11419/450
Bibliographic Reference: Georgiou, D., Antoniou, E., & Chatzimichailidis, A. (2015). Kruskal's algorithm [Simulation]. In Georgiou, D., Antoniou, E., & Chatzimichailidis, A. 2015. Discrete Mathematical Structures in Computer Science [Undergraduate textbook]. Kallipos, Open Academic Editions. chapter 4. http://hdl.handle.net/11419/450
Language: Greek
Is Part of: GRAPHS AND APPLICATIONS
Interactivity Level: 0
Difficulty: very low
Typical Learning Time: PT00H10M00S
Publication Origin: Kallipos, Open Academic Editions