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
| % Programme de l'Arbre Couvrant de Poids Miniumum (ACPM)
%-------------------------------------------------------
%
clear all;
clc
% les données
Ns=5; % nombre de sommet
So=[1 2 3 4 5]'; % les sommets
Nr=7; % nombre d'arètes
% les arètes
Ar(1,2)=1; Ar(1,4)=1; Ar(2,3)=1;Ar(2,4)=1; Ar(3,4)=1; Ar(3,5)=1; Ar(4,5)=1;
% les poids
Pds(1,2)=35; Pds(1,4)=40; Pds(2,3)=10;Pds(2,4)=25; Pds(3,4)=20; Pds(3,5)=30; Pds(4,5)=15;
% les boucles
% Nb=6;
% Bou=[1 2 2 4 1 4; 1 2 3 4 1 0; 1 2 3 5 4 1; 2 3 4 2 0 0; 2 3 5 4 2 0; 3 4 5 3 0 0];
% tri
M=[];
for i=1:Ns
for j=i+1:Ns
if Ar(i,j)~=0
TR=Pds(i,j);
M=[M;i,j,TR];
end
end
end
[a,b]=sort(M(:,3));
XX=M(b,1:3);
% parcours du graphe
YY=XX(:,1:2);
MM=YY';
KK=MM(:);
for j=1:length(KK)-2
for k=j+1:length(KK)-1
for h=k+1:length(KK)-1
if KK(j)==KK(k)& KK(j)==KK(h)
KK(h)=[]
end
end
end
end |
Partager