What does this means
The edges of the minimum spanning tree are returned in array mst (of size n-1 by 2)
?
When I run the program, at some point displays
however I don't know how to interpret this as edges of the minimum spanning tree.
How do I take the edges? Is there a way to plot this answer?
Could someone help please?
This is the 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)
An edge can be uniquely identified by the two vertices that it joins.
Each row of mst
contains the two indices to the two vertices that span the edge.
The input graph is composed of a set of vertices and edges joining them, represented as an adjacency matrix A
. If A(i,j)
is true, then vertices i and j are adjacent (i.e. share an edge). In the output matrix mst
this edge would be represented by mst(index,:) = [i,j]
.