Como Graficar El algoritmo de Prim
Publicado por Leandro (1 intervención) el 11/05/2011 16:06:16
COMO LE HAGO PARA GRAFICAR LAS ARISTAS QUE SE UNES, PERO PAUSANDO EN CADA INTERACION, ES DECIR QUE SE MUESTRE ARISTA POR ARISTA
%tengo el algoritmo de prim
function [mst, cost] = prim(A)
% El usuario suministra una matriz A que es la matriz de adyacencia que
% caracteriza al grafo. Este programa hace uso del Algoritmo de Prim para
% encontrar un árbol de expansión mínima.This program uses. Las aristas del
% árbol de expansión minima se guardan en el arreglo mst {de tamaño n-1 por
% 2}, y el costo total e guardado en la variable cost. El programa muestra
% en la variable y hace una pausa para que el usuario puede ver lo que está
% sucediendo. Para continuar después de una pausa, pulse cualquier
% tecla.A=[0 6 1 5 0 0; 6 0 5 0 3 0; 1 5 0 5 6 4; 5 0 5 0 0 2; 0 3 6 0 0 6; 0 0 4 2 6 0]
disp('ejemplo : [0 6 1 5 0 0; 6 0 5 0 3 0; 1 5 0 5 6 4; 5 0 5 0 0 2; 0 3 6 0 0 6; 0 0 4 2 6 0]')
A=input('INGRESE LOS VALORES DE LA MATRÍZ: ');
[n,n] = size(A); % Matriz de tamaño n por n, donde n = # nodos.
A,
n,
pause,
if norm(A-A','fro') ~= 0 , % Si la matriz de adyacencia no es simetrica,
disp(' Error: La matriz de Adyacencia debe ser simétrica ') % Imprime un mensaje de error y sale.
return,
end;
% Comienza con el nodo 1 y hacer un seguimiento de cuales nodos están en el
% árbol y cuales no lo están.
intree = [1];
number_in_tree = 1;
number_of_edges = 0;
notintree = [2:n]';
number_notin_tree = n-1;
in = intree(1:number_in_tree), % imprime los nodos que están en el árbol
out = notintree(1:number_notin_tree), pause, % y cuales no.
% Iterar hasta que todos los n nodos están en el árbol.
while number_in_tree < n,
% Find the cheapest edge from a node that is in tree to one that is not.
mincost = Inf; % You can actually enter infinity into Matlab.
for i=1:number_in_tree,
for j=1:number_notin_tree,
ii = intree(i); jj = notintree(j);
if A(ii,jj) < mincost && A(ii,jj) ~= 0,
mincost = A(ii,jj);
jsave = j;
iisave = ii;
jjsave = jj; % Save coords of node.
end;
end;
end;
% Add this edge and associated node jjsave to tree. Delete node jsave from list
% of those not in tree.
number_of_edges = number_of_edges + 1; % Increment number of edges in tree.
mst(number_of_edges,1) = iisave; % Add this edge to tree.
mst(number_of_edges,2) = jjsave;
costs(number_of_edges,1) = mincost;
number_in_tree = number_in_tree + 1; % Increment number of nodes that tree connects.
intree = [intree; jjsave]; % Add this node to tree.
for j=jsave+1:number_notin_tree, % Delete this node from list of those not in tree.
notintree(j-1) = notintree(j);
end;
number_notin_tree = number_notin_tree - 1; % Decrement number of nodes not in tree.
in = intree(1:number_in_tree), % Print which nodes are now in tree and
out = notintree(1:number_notin_tree), pause,% which are not.
end;
disp(' Aristas en el árbol de expansión mínimo y sus costos ')
[mst costs] % Print out edges in minimum spanning tree.
cost = sum(costs)
disp('Aristas que Se Unen')
%como hago para graficar las aristas que se unen
%gracias!!!
%tengo el algoritmo de prim
function [mst, cost] = prim(A)
% El usuario suministra una matriz A que es la matriz de adyacencia que
% caracteriza al grafo. Este programa hace uso del Algoritmo de Prim para
% encontrar un árbol de expansión mínima.This program uses. Las aristas del
% árbol de expansión minima se guardan en el arreglo mst {de tamaño n-1 por
% 2}, y el costo total e guardado en la variable cost. El programa muestra
% en la variable y hace una pausa para que el usuario puede ver lo que está
% sucediendo. Para continuar después de una pausa, pulse cualquier
% tecla.A=[0 6 1 5 0 0; 6 0 5 0 3 0; 1 5 0 5 6 4; 5 0 5 0 0 2; 0 3 6 0 0 6; 0 0 4 2 6 0]
disp('ejemplo : [0 6 1 5 0 0; 6 0 5 0 3 0; 1 5 0 5 6 4; 5 0 5 0 0 2; 0 3 6 0 0 6; 0 0 4 2 6 0]')
A=input('INGRESE LOS VALORES DE LA MATRÍZ: ');
[n,n] = size(A); % Matriz de tamaño n por n, donde n = # nodos.
A,
n,
pause,
if norm(A-A','fro') ~= 0 , % Si la matriz de adyacencia no es simetrica,
disp(' Error: La matriz de Adyacencia debe ser simétrica ') % Imprime un mensaje de error y sale.
return,
end;
% Comienza con el nodo 1 y hacer un seguimiento de cuales nodos están en el
% árbol y cuales no lo están.
intree = [1];
number_in_tree = 1;
number_of_edges = 0;
notintree = [2:n]';
number_notin_tree = n-1;
in = intree(1:number_in_tree), % imprime los nodos que están en el árbol
out = notintree(1:number_notin_tree), pause, % y cuales no.
% Iterar hasta que todos los n nodos están en el árbol.
while number_in_tree < n,
% Find the cheapest edge from a node that is in tree to one that is not.
mincost = Inf; % You can actually enter infinity into Matlab.
for i=1:number_in_tree,
for j=1:number_notin_tree,
ii = intree(i); jj = notintree(j);
if A(ii,jj) < mincost && A(ii,jj) ~= 0,
mincost = A(ii,jj);
jsave = j;
iisave = ii;
jjsave = jj; % Save coords of node.
end;
end;
end;
% Add this edge and associated node jjsave to tree. Delete node jsave from list
% of those not in tree.
number_of_edges = number_of_edges + 1; % Increment number of edges in tree.
mst(number_of_edges,1) = iisave; % Add this edge to tree.
mst(number_of_edges,2) = jjsave;
costs(number_of_edges,1) = mincost;
number_in_tree = number_in_tree + 1; % Increment number of nodes that tree connects.
intree = [intree; jjsave]; % Add this node to tree.
for j=jsave+1:number_notin_tree, % Delete this node from list of those not in tree.
notintree(j-1) = notintree(j);
end;
number_notin_tree = number_notin_tree - 1; % Decrement number of nodes not in tree.
in = intree(1:number_in_tree), % Print which nodes are now in tree and
out = notintree(1:number_notin_tree), pause,% which are not.
end;
disp(' Aristas en el árbol de expansión mínimo y sus costos ')
[mst costs] % Print out edges in minimum spanning tree.
cost = sum(costs)
disp('Aristas que Se Unen')
%como hago para graficar las aristas que se unen
%gracias!!!
Valora esta pregunta
0
