-
Notifications
You must be signed in to change notification settings - Fork 0
/
grMinSpanTree.m
63 lines (59 loc) · 2.12 KB
/
grMinSpanTree.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
function nMST=grMinSpanTree(E)
% Function nMST=grMinSpanTree(E) solve
% the minimal spanning tree problem for a connected graph.
% Input parameter:
% E(m,2) or (m,3) - the edges of graph and their weight;
% 1st and 2nd elements of each row is numbers of vertexes;
% 3rd elements of each row is weight of edge;
% m - number of edges.
% If we set the array E(m,2), then all weights is 1.
% Output parameter:
% nMST(n-1,1) - the list of the numbers of edges included
% in the minimal (weighted) spanning tree in the including order.
% Uses the greedy algorithm.
% Author: Sergii Iglin
% e-mail: [email protected]
% personal page: http://iglin.exponenta.ru
% ============= Input data validation ==================
if nargin<1,
error('There are no input data!')
end
[m,n,E] = grValidation(E); % E data validation
% ============= The data preparation ==================
En=[(1:m)',E]; % we add the numbers
En(:,2:3)=sort(En(:,2:3)')'; % edges on increase order
ln=find(En(:,2)==En(:,3)); % the loops numbers
En=En(setdiff([1:size(En,1)]',ln),:); % we delete the loops
[w,iw]=sort(En(:,4)); % sort by weight
Ens=En(iw,:); % sorted edges
% === We build the minimal spanning tree by the greedy algorithm ===
Emst=Ens(1,:); % 1st edge include to minimal spanning tree
Ens=Ens(2:end,:); % rested edges
while (size(Emst,1)<n-1)&(~isempty(Ens)),
Emst=[Emst;Ens(1,:)]; % we add next edge to spanning tree
Ens=Ens(2:end,:); % rested edges
if any((Emst(end,2)==Emst(1:end-1,2))&...
(Emst(end,3)==Emst(1:end-1,3))) | ...
IsCycle(Emst(:,2:3)), % the multiple edge or cycle
Emst=Emst(1:end-1,:); % we delete the last added edge
end
end
nMST=Emst(:,1); % numbers of edges
return
function ic=IsCycle(E); % true, if graph E have cycle
n=max(max(E)); % number of vertexes
A=zeros(n);
A((E(:,1)-1)*n+E(:,2))=1;
A=A+A'; % the connectivity matrix
p=sum(A); % the vertexes power
ic=false;
while any(p<=1), % we delete all tails
nc=find(p>1); % rested vertexes
if isempty(nc),
return
end
A=A(nc,nc); % new connectivity matrix
p=sum(A); % new powers
end
ic=true;
return