5.4最小生成树

#include  " stdafx.h "
#include  < iostream.h >
#include  < malloc.h >

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;
}
    
对于这个普里姆算法,书上讲的有些不太细致,主要表现在U和TE的定义,以及对于辅助数组的作用的说明(也可能是我的理解能力差吧.).我看了两天都没有看明白书上的算法,我参考了严蔚敏的数据结构后,才逐渐的明白.
我对于书上不明白的地方写一下我自己的认识:
(1)U:是指对于新增加的顶点的集合,那么在初始状态时,我们加入一个新的顶点时,它的集合为:U={u0}.
(2)TE:是指最小生成树边的集合,也就是使权最小的边的集合.
(3)V-U:指在所有顶点中,去除U后所剩的顶点.
那么普里姆算法中,最简洁明了的说明是:"每新增一个顶点,就找到这个顶点到其它顶点的最小权,来更新辅助数组中的权值".这就涉及到了这个辅助数组的作用:
(4)辅助数组closedge:closedge数组的长度顶点的数量,其中记录的是U中顶点对V-U中顶点连通的权值.那么这个数组的更新就是在每向U中增加一个顶点的时候,就从这个新的顶点找到它与其它顶点连通的边的权值,与辅助数组中的记录的上次的顶点的权值做一个比较,如果小则更新之.在辅助数组中,lowcost=0代表此结点已经加入U中(例如closedge[0].lowcost=0,说明V0顶点已经加入到U中),lowcost=MAX表示尚未连通此顶点.

以我上面实现的代表为例,辅助数组的变化情况如下表:

转载于:https://www.cnblogs.com/fxwdl/archive/2007/07/30/836037.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！