Was bedeutet das
Die Kanten des minimalen Spannbaums werden im Array mst (der Größe n-1 mal 2) zurückgegeben
?
Wenn ich das Programm starte, wird irgendwann angezeigt
Ich weiß jedoch nicht, wie ich dies als Kanten des minimalen Spannbaums interpretieren soll.
Wie nehme ich die Kanten? Gibt es eine Möglichkeit, diese Antwort zu plotten?
Könnte bitte jemand helfen?
Dies ist der Code.
function [mst, cost] = prim(A)
[n,n] = size(A);
A, n, pause,
if norm(A-A','fro') ~= 0 ,
disp(' Error: Adjacency matrix must be symmetric ')
return,
end;
intree = [1]; number_in_tree = 1;
number_of_edges = 0;
notintree = [2:n]'; number_notin_tree= n-1;
in = intree(1:number_in_tree),
out = notintree(1:number_notin_tree),
pause,
while number_in_tree < n,
mincost = Inf;
for i=1:number_in_tree,
for j=1:number_notin_tree,
ii = intree(i); jj =
notintree(j);
if A(ii,jj) < mincost,
mincost = A(ii,jj); jsave = j;
iisave = ii; jjsave = jj;
end;
end;
end;
number_of_edges = number_of_edges +1;
mst(number_of_edges,1) = iisave;
mst(number_of_edges,2) = jjsave;
costs(number_of_edges,1) = mincost;
number_in_tree = number_in_tree + 1;
intree = [intree; jjsave];
for j=jsave+1:number_notin_tree,
notintree(j-1) = notintree(j);
end;
number_notin_tree = number_notin_tree - 1;
in = intree(1:number_in_tree),
out = notintree(1:number_notin_tree),
pause,
end;
disp(' Edges in minimum spanning tree and their costs: ')
[mst costs]
cost = sum(costs)
Eine Kante kann durch die beiden Knoten, die sie verbindet, eindeutig identifiziert werden. Jede Reihe von mst
enthält die beiden Indizes zu den beiden Scheitelpunkten, die die Kante überspannen.
Der Eingabegraph besteht aus einem Satz von Scheitelpunkten und Kanten, die diese verbinden, dargestellt als Adjazenzmatrix A
. Wenn A(i,j)
wahr, dann sind die Scheitelpunkte i und j benachbart (dh teilen sich eine Kante). In der Ausgabematrix mst
würde diese Kante durch dargestellt werden mst(index,:) = [i,j]
.
Dieser Artikel stammt aus dem Internet. Bitte geben Sie beim Nachdruck die Quelle an.
Bei Verstößen wenden Sie sich bitte [email protected] Löschen.
Lass mich ein paar Worte sagen