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
>>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)
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
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?
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.
the code is very simple to understand and use.
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"
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...!
je voudrais savoir
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.
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.
not simply to use, a real mess! :)
Simple and easy to use !
I promise to update soon the documentation. But now I have a problem and I can't