最小生成树的两个程序，prim算法

１、第一个是C++的，用的是prim算法：

#include "iostream"
#include "malloc.h"

using namespace std;

int const vnum=6;
int const MAX=32767;

typedef struct graph
{
    int vexs[vnum]; //顶点信息

    int arcs[vnum][vnum]; //边的信息,因为现在是求带权图的最小生成树,所以其值为权值

    int vexnum; //顶点数量

    int arcnum; //边的数量

}GraphTp;

typedef struct
{
    int adjvex; //代表新增结点的编号

    //代表新增结点对于i的结点的权值.

    //所谓的i就是Closege[vnum]数组中的值,vnum从0至vnum-1,代表第0至vnum-1个结点的编号,也即closege数组中的一个值,代表

    //U中的结点编号,对就于V-U中的某结点的权值.例如对于Closege[0]来说,adjvex=3,lowcost=1,则说明这是U中的第3个结点对于

    //于V-U中的第0个结点的权值为1

    int lowcost;
}Closege[vnum];

void CreateGraph(GraphTp & graph)
{
    graph.vexnum=vnum;
    graph.arcnum=10;

    int k=0;
    graph.vexs[k]=k;
    graph.arcs[k][0]=MAX;
    graph.arcs[k][1]=6;
    graph.arcs[k][2]=1;
    graph.arcs[k][3]=5;
    graph.arcs[k][4]=MAX;
    graph.arcs[k][5]=MAX;

    k=1;
    graph.vexs[k]=k;
    graph.arcs[k][0]=6;
    graph.arcs[k][1]=MAX;
    graph.arcs[k][2]=5;
    graph.arcs[k][3]=MAX;
    graph.arcs[k][4]=3;
    graph.arcs[k][5]=MAX;

    k=2;
    graph.vexs[k]=k;
    graph.arcs[k][0]=1;
    graph.arcs[k][1]=5;
    graph.arcs[k][2]=MAX;
    graph.arcs[k][3]=5;
    graph.arcs[k][4]=6;
    graph.arcs[k][5]=4;

    k=3;
    graph.vexs[k]=k;
    graph.arcs[k][0]=5;
    graph.arcs[k][1]=MAX;
    graph.arcs[k][2]=5;
    graph.arcs[k][3]=MAX;
    graph.arcs[k][4]=MAX;
    graph.arcs[k][5]=2;

    k=4;
    graph.vexs[k]=k;
    graph.arcs[k][0]=MAX;
    graph.arcs[k][1]=3;
    graph.arcs[k][2]=6;
    graph.arcs[k][3]=MAX;
    graph.arcs[k][4]=MAX;
    graph.arcs[k][5]=6;

    k=5;
    graph.vexs[k]=k;
    graph.arcs[k][0]=MAX;
    graph.arcs[k][1]=MAX;
    graph.arcs[k][2]=4;
    graph.arcs[k][3]=2;
    graph.arcs[k][4]=6;
    graph.arcs[k][5]=MAX;

}

//输入最小生成树,K为第K个机点,索引从0开始

void prim(GraphTp graph,int k)
{
    Closege closege;
    int i;
    //初始化辅助数组,使其结点

    for(i=0;i<vnum;i++)
    {
        if (i!=k)
        {
            closege[i].adjvex=graph.vexs[k];
            closege[i].lowcost=graph.arcs[k][i];
        }
    }
    closege[k].adjvex=graph.vexs[k];
    closege[k].lowcost=0;
    cout<<"在U中首次加入顶点:"<<graph.vexs[k]<<endl;
    //控制次数,因为至多加个vnum个顶点,而初始时已加入一个,所以循环的次数为vnum-1次

    for (i=1;i<vnum;i++)
    {
        int min=-1; //记录最小的权

        int v=-1; //记录最小的权所对就的closege中的索引值

        //找到当前权值最小的边

        for(int j=0;j<vnum;j++)
        {
            if (closege[j].lowcost>0 && closege[j].lowcost!=MAX)
            {
                if (min==-1)
                {
                    min=closege[j].lowcost;
                    v=j;
                }
                else
                {
                    if (min>closege[j].lowcost)
                    {
                        min=closege[j].lowcost;
                        v=j;
                    }
                }
            }
        }
        cout<<"在U中加入顶点:"<<v<<",权值为:"<<min<<endl;
        //修改closege[v].lowcost的值为0,代表共已经加入了U中

        closege[v].lowcost=0;
        //以新加入的顶点,与各顶点的权值,更新closege中的权值以及顶点,此为关键,这是保证closege这个辅助数组起作用的关键

        for(int k=0;k<vnum;k++)
        {
            if (graph.arcs[v][k] < closege[k].lowcost)
            {
                closege[k].lowcost = graph.arcs[v][k];
                closege[k].adjvex = v;
            }
        }
    }
}

int main(int argc, char* argv[])
{
    GraphTp g;
    CreateGraph(g);
    prim(g,0);
    return 0;
}

２、为了方便处理数据，我又实现了一个matlab的程序，输入为一个图的邻接矩阵，下面是m文件：

function [answer costanswervector]=prim(matrix)
    answervector=[];
    costanswervector=[];
    
    helpvector=[];
    lowcostvector=[];
    
    vexnum=size(matrix,1);
    
    lowcostvector(1)=0;
    for i=1:1:vexnum,
        if i~=1,
            helpvector=[helpvector i];
            lowcostvector=[lowcostvector matrix(1,i)];
        end
    end
    
    answervector(1)=1;
        
    for i=2:1:vexnum,
        min=-1;
        v=-1;
        
        for j=1:1:vexnum
            if (lowcostvector(j)>0) & (lowcostvector(j)~=32767),
                if min==-1,
                    min=lowcostvector(j);
                    v=j;
                else
                    if min>lowcostvector(j),
                        min=lowcostvector(j);
                        v=j;
                    end
                end
            end
        end
        answervector=[answervector v];
        costanswervector=[costanswervector min];
        
        lowcostvector(v)=0;
        
        for k=1:1:vexnum,
            if matrix(v,k) < lowcostvector(k),
                lowcostvector(k)=matrix(v,k);
                helpvector(k)=v;
            end
        end
    end
    
    answervector
    costanswervector