3.625

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

Kruskal Algorithm

by

 

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

| Watch this File

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)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (15)
09 Oct 2012 Anand  
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.

01 May 2012 Mohamed Reda  
26 Jun 2011 Rosiana Prabandari

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

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

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

15 Oct 2008 kheroua mohalled reda

je voudrais savoir

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.

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

Contact us