prim.m

来自「最小生成树 采用C程序编程实现的PRIM算法」· M 代码 · 共 39 行

function [p,data]=prim(a,e)   
%在数据结构课程设计之余,即兴之作吧
%最小生成树的prim算法
%a为邻接矩阵，e为出发的顶点的序号
%p返回的是最小生成树的邻接矩阵
%data记录最后最小生成树的权值
data=0;
m=length(a);        %图的顶点个数
if e>m|e<1
    fprintf('e值越界！');
else
b=e;                %b存储已经入树的顶点的号码，顶点编号默认从1到n   
p=zeros(m,m);
for i=1:m
    for j=1:m
         c(i,j)=inf;
     end
end
while length(b)<m       %树中顶点个数不足m
    for i=1:length(b)
        c(i,:)=a(b(i),:);
    end
    [x,y]=ind2sub(size(c),find(c==min(min(c))));   %当前c中最小元素在c中的双下标表示
    y=y(1);
    k=find(a(:,y)==min(min(c)));                   %在a中找到这个元素的位置（列位置已知为y）
    for i=1:length(k)                              %确定这个元素的行位置k
        if any(b==k(i))
            k=k(i); break;
        end
    end
    if ~any(b==y)
        b(length(b)+1)=y;
        p(k,y)=1; p(y,k)=1;
        data=data+a(k,y);
    end
        a(k,y)=inf;
        a(y,k)=inf;
end
end