View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Kruskal Algorithm

2.5 | 9 ratings Rate this file 12 Downloads (last 30 days) File Size: 3.11 KB File ID: #13457 Version: 1.0

Kruskal Algorithm



Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connect

| Watch this File

File Information

Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected un directed weighted graph

The zip file contains

kruskal.m iscycle.m fysalida.m connected.m

If we want to find the minimum spanning tree. We call function kruskal.

% Input: PV = nx3 martix. 1st and 2nd row's define the edge (2 vertices) and
% the 3rd is the edge's weight
% Output: w = Minimum spanning tree's weight
% T = Minimum spanning tree's adjacency matrix

example :

>>PV = PV = [ 1 2 5;1 3 8;1 5 10;2 3 10;3 4 4;3 5 7;4 5 6];

>>[w T] = kruskal(PV)

w =


T =

     0 1 1 0 0
     1 0 0 0 0
     1 0 0 1 0
     0 0 1 0 1
     0 0 0 1 0

MATLAB release MATLAB 6.5 (R13)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (17)
20 Jan 2017 Swagata Biswas

18 Sep 2016 Giang Nguyen

I see that Kruskal's algorithm can good running on Math with small data. When I input matrix "PV" has 14338*3 size, Matlab show the mistake

Attempted to access X(76,0); index must be a positive integer or logical.

Error in kruskal (line 18)
X(PV(i,1),PV(i,2)) = 1;

Error in mess (line 3)
[w T] = kruskal(PV)

I don't understand why. Can you explain for me?

Comment only
09 Oct 2012 Anand

Anand (view profile)

14 May 2012 Peet Le Roux

Can someone please tell me what is wrong with the coding of the connected function? I recoded this function and still don’t understand what could be wrong. I understand the code so if someone can maybe just give me a hint please.

Comment only
01 May 2012 Mohamed Reda

26 Jun 2011 Rosiana Prabandari

the code is very simple to understand and use.

Comment only
23 Dec 2008 Billal merabti

the code of 'connected' function is not correct. if you want to use this code you have to correct it (it is simple to do). but i think that the code is verry simple to understand and to use.
an other think, we can use the matlab function max(PV,3)' in the place of "fysalida.m"

Comment only
15 Oct 2008 kheroua mohammed reda

a kadri celui que je connais le prof. de geologie a l'ecole des mines de oui j'aimerais renrer en contact...!

Comment only
15 Oct 2008 kheroua mohalled reda

je voudrais savoir

Comment only
31 May 2008 Lai Wei

I think the code is not correct. If we get w=[0 1 0 0;1 0 1 0;0 1 0 0;0 1 0 0], the connected will also be 1.

Comment only
11 May 2008 kadri mourad

29 Sep 2007 Jonathan Primof

25 Apr 2007 Guillaume Bouchard

I compared this code to the PRIM algortihm
on a dense adjacency matrix of size (100x100):
0.0578 seconds for PRIM algorithm
64.9045 seconds for Kruskal method
This is a huge difference!
Theoretically, the two algorithms have a similar complexity, so I think this code should be improved.

18 Feb 2007 Greg Mardis

08 Feb 2007 John Litmaier

not simply to use, a real mess! :)

29 Jan 2007 Anima Kumar

Simple and easy to use !

21 Dec 2006 Nick Cheilakos

I promise to update soon the documentation. But now I have a problem and I can't

Comment only

Contact us