Найти минимальное связующее дерево - PullRequest
Новая
       46

Найти минимальное связующее дерево

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

Не могли бы вы сказать, почему этот код MATLAB неверен?Я не понимаю почему.Заранее большое спасибо. 

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)

Когда я нажимаю кнопку запуска, появляется сообщение: 

Not enough input arguments.

Error in prim (line 10)
[n,n] = size(A);
% The matrix is n by n, where n = # nodes.

Однако, когда я вызываю функцию в окне команд с помощью 

s=[1 1 2 2 2 3 3 4 4 4 5 5 6 7];
t=[2 3 4 5 3 5 6 5 7 8 6 8 7 8];
w=[3 5 4 7 4 9 8 3 11 8 3 9 8 7];
G = graph(s,t,w);
A = adjacency(G);
prim(A)

Код работает «правильно»

В качестве окончательного ответа возвращается

mst =

cost=

All zero sparse: 1-by-1

Должно быть возвращено

mst =

1 2

2 3

2 4

4 5

5 6

6 7

7 8

стоит = 32

Почему это не вернулось?

Во время работы программа перешла с 1 на 4, хотя она должна была перейти на 2. Затем с 4 до 5, это было правильно, но я не знаю, почему пропустили 2 и 3 иперешли непосредственно к 4,5,6,7,8.

Помогите мне, пожалуйста.

Если есть альтернативный код, который вы знаете, укажите его, возможно, более простой.

1 Ответ

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

Основная проблема с вашей функцией заключается в том, что когда вы проверяете, имеет ли текущее ребро более низкую стоимость, чем mincost, вы не проверяете, что на самом деле там есть ребро.Если нет никакого края, то стоимость будет 0, что, естественно, ниже, чем любое положительное значение стоимости.Вам необходимо изменить строку: 

if A(ii,jj) < mincost,

на 

if (A(ii,jj) > 0) && (A(ii,jj) < mincost), % A(ii,jj) is edge and lower cost than mincost

Матрица смежности, используемая в качестве ввода: 

A =

    0    3    5    0    0    0    0    0
    3    0    4    4    7    0    0    0
    5    4    0    0    9    8    0    0
    0    4    0    0    3    0   11    8
    0    7    9    3    0    3    0    9
    0    0    8    0    3    0    8    0
    0    0    0   11    0    8    0    7
    0    0    0    8    9    0    7    0

Выход после этого изменения: 

mst =

   1   2
   2   3
   2   4
   4   5
   5   6
   4   8
   8   7

cost =  32
...