File Exchange

image thumbnail

Kruskal Algorithm

version 1.0 (3.11 KB) by

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

2.46154
9 Ratings

21 Downloads

Updated

View License

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

Comments and Ratings (17)

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?

Anand

Anand (view profile)

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.

Mohamed Reda

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

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

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

kheroua mohalled reda

je voudrais savoir

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.

kadri mourad

Jonathan Primof

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.

Greg Mardis

John Litmaier

not simply to use, a real mess! :)

Anima Kumar

Simple and easy to use !

Nick Cheilakos

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

MATLAB Release
MATLAB 6.5 (R13)

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

» Watch video