找到最小的生成树 [英] Find a minimum spanning tree

问题描述

能否请您告诉我为什么此MATLAB代码错误?我不明白为什么.提前非常感谢您.

Could you please tell me why this MATLAB code is wrong? I don't understand why. Thank you so much in advance.

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)

当我单击运行"按钮时，会说:

When I click the run button says:

Not enough input arguments.

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

但是，当我使用以下命令在命令"窗口中调用函数时:

However when I call the function in the Command window with

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

它应该已经回来了

It should have returned

mst =

1 2

2 3

2 4

4 5

5 6

6 7

7 8

costs = 32

costs=32

---

为什么没有退还那笔钱?

---

Why did not returned that?

虽然运行程序应该从1转到4，但是应该从4转到5，这是正确的，但是我不知道为什么跳过2和3并直接转到4,5,6， 7,8.

Whilst running the program went from 1 to 4 though it should have gone to 2. Then from 4 to 5, that was correct but I don't know why skipped 2 and 3 and went directly to 4,5,6,7,8.

请帮助我.

如果您知道其他代码，请提供，可能更简单.

If there is an alternative code that you know please provide it, perhaps an easier one.

推荐答案

该函数的主要问题是，当您检查当前边的成本是否低于mincost时，您不会验证是否确实存在那里的边缘.如果没有优势，则成本将为0，自然低于任何正成本值.您需要更改以下行:

The main problem with your function is that when you check to see if the current edge has lower cost than mincost, you don't verify that there's actually an edge there. If there's no edge, then the cost will be 0, which is naturally lower than any positive cost value. You need to change the line:

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

这篇关于找到最小的生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！