Dada la matriz de adyacencia a del gráfico, intente dar el árbol de expansión mínimo del gráfico. programación matlab
Le proporciona una función de llamada de árbol de expansión mínima. Copie su número de vértice en n y la matriz de adyacencia en W.
Luego llame a mintree(n,W)
función [Wt,Pp]=mintree(n,W)
% para encontrar el árbol de expansión mínimo, n es el número de vértices, y W es la matriz de adyacencia de valores de peso, los no adyacentes están representados por inf
%Wt es el peso del árbol de expansión mínimo, Pp (:, 1:2) representa los dos vértices del árbol de expansión mínimo árbol de expansión
% Pp(:, 4) representa el número de secuencia del árbol de expansión mínimo
tmpa=find(W~=inf);
[ tmpb,tmpc]=find(W~=inf);
w=W(tmpa);
e=[tmpb,tmpc];
[ wa,wb]=sort(w);
E=[e(wb,:),wa,wb];
[nE,mE]=tamaño(E);
temp=buscar(E( :,1)-E(:,2));
E=E(temp,:);
P =E(1,:);
k=longitud(E(:,1));
mientras rango(E)>0
temp1= max(E(1,2),E(1, 1));
temp2=min(E(1,2),E(1,1));
para i=1:k
si E(i,1)==temp1
E(i,1)=temp2;
fin
si E(i,2)== temp1
E(i,2)=temp2;
fin
fin
a=find(E(:,1) -E(:,2));
E=E(a,:);
si rango(E) >0
P=[P ;E(1,:)];
k=longitud(E(:,1));
fin
fin
Peso=sum(P(:,3))
Pp=[e(P(:,4),:),P(: ,3:4)];
for i=1:length(P(:,3))
disp(['','e',num2str(P(i ,4)),'',... p>
'(v',num2str(P(i,1)),'','v',num2str(P(i,2)), ')']);
fin
eje igual;% dibuja un árbol de expansión mínimo
mantén presionado
[x,y ]=cilindro(1,n);
xm=min(x(1,:));
ym=min(y(1,:));
xx=max(x(1,:) );
yy=max(y(1,:));
eje([xm-abs(xm )*0.15,xx+abs(xx)*0.15,ym -abs(ym)*0.15,yy+abs(yy)*0.15]);
plot(x(1,:),y (1,:),'ko');
for i=1:n
temp=['v',int2str(i)];
text(x(1,i),y(1, i),temp);
end
para i=1:nE
plot( x(1,e(i,:)),y( 1,e(i,:)),'b');<
/p>
fin
para i=1:longitud(P(:,4))
plot(x(1,Pp(i,1:2)) ,y(1,Pp(i,1:2)),'r');
end
text(-0.35,-1.2,['El peso del mínimo el árbol de expansión es','',num2str(Wt)]);
title('La línea roja es el árbol de expansión mínimo');
eje fuera;
esperar;