Kruskal Algorithm

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

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)
• Other Files: MST_Kruskal/connected.m, ; MST_Kruskal/fysalida.m, ; MST_Kruskal/iscycle.m, ; MST_Kruskal/kruskal.m

[Nick Cheilakos]

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

[Anima Kumar]

Simple and easy to use !

[John Litmaier]

not simply to use, a real mess! :)

[Greg Mardis]

 

[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.

[Jonathan Primof]

 

[kadri mourad]

 

[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.

[kheroua mohalled reda]

je voudrais savoir

[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...!

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