Search code examples
arraysmatlabmathtreeminimum-spanning-tree

Interpreting an answer given as two arrays


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

this two arrays

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)

Solution

  • 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].