Интерпретация ответа в виде двух массивов - PullRequest
Новая
       30

Интерпретация ответа в виде двух массивов

0 голосов
/ 05 декабря 2018

Что это значит

Края минимального остовного дерева возвращаются в массиве mst (размером n-1 на 2)

?

Когда я запускаю программу, в какой-то момент отображаются

эти два массива

однако я не знаю, как интерпретировать это как ребра минимального охватадерево.

Как взять края?Есть ли способ построить этот ответ?

Может ли кто-нибудь помочь, пожалуйста?

Это код. 

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)

1 Ответ

0 голосов
/ 05 декабря 2018

Ребро может быть однозначно идентифицировано двумя вершинами, к которым оно присоединяется.Каждая строка mst содержит два индекса для двух вершин, которые охватывают ребро.

Входной граф состоит из набора вершин и ребер, соединяющих их, представленных в виде матрицы смежности A.Если A(i,j) истинно, то вершины i и j являются смежными (то есть разделяют ребро).В выходной матрице mst этот край будет представлен как mst(index,:) = [i,j].

...