Red de conocimiento informático - Conocimiento informático - Dada la matriz de adyacencia a del gráfico, intente dar el árbol de expansión mínimo del gráfico. programación matlab

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)),'',...

'(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;