Code covered by the BSD License

### Highlights from Kruskal Algorithm

3.625
3.6 | 8 ratings Rate this file 15 Downloads (last 30 days) File Size: 3.11 KB File ID: #13457 Version: 1.0

# Kruskal Algorithm

### Nickolas Cheilakos (view profile)

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

File Information
Description

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 =

23

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)
09 Oct 2012 Anand

### Anand (view profile)

14 May 2012 Peet Le Roux

### Peet Le Roux (view profile)

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

### Mohamed Reda (view profile)

26 Jun 2011 Rosiana Prabandari

### Rosiana Prabandari (view profile)

the code is very simple to understand and use.
thanks.

Comment only
23 Dec 2008 Billal merabti

### Billal merabti (view profile)

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"
thanks

Comment only
15 Oct 2008 kheroua mohammed reda

a kadri mourad...es-tu celui que je connais le prof. de geologie a l'ecole des mines de paris...si 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
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