Prim最小生成树算法

（程序设计类课程）

实验报告

福建农林大学计算机与信息学院实验报告

系：    计算机与信息      专业： 计算机科学与技术(专升本)  年级：     08级             

姓名：    许章赫     学号：  0818060   实验室号 田家炳513计算机号         

实验三 Prim最小生成树算法

一、实验目的和要求

●理解图的遍历

●理解构造无向联通图的最小生成树的方法（Prim算法算法）

●能用Prim算法或Kruskal算法构造最小生成树出来

●区别Prim算法与Kruskal算法

二、实验内容和原理

        ⑴ 实验内容：

用Prim算法或Kruskal算法构造一颗最小生成树（本人在本实验中选择用Prim算法）

        (2) 实验原理：

          ①从网中任一顶点开始，先把该顶点包含在生成树中，此时生成树只有

一个顶点。

②找出一个端点在生成树中另一端点在生成树外的所有边，并把权值最

小的边连到同它所关联的另一个顶点添加到生成树中；当有两条及以

上具有相同最小权值的边可供选择时，任选一条。

③反复执行②，直到所有顶点都包含在生成树时为止。

三、实验环境

硬件：

（1）学生用微机

（2）多媒体实验教室

软件：

（1）Windows XP中文操作系统 

（2）Visual Studio 2005

四、算法描述及实验步骤

1、算法描述

     例：有向图

（a）初态    （b）一条边      （c）两条边          （d）三条边

 （e）四条边          （f）五条边                     （g）终态

2、N-S表示

    3、代码(注释)

#include "stdio.h"

#include "conio.h"

#include "malloc.h"

#define N0 10

#define infi 32767

typedef int AdjMatrix[N0+1][N0+1];

typedef struct arcnode

{ 

    int v,w;

    struct arcnode *next;

}ArcNode;

AdjMatrix adjmatrix;

int n;  //邻接矩阵的行列数

void createAdj()

{ 

    int i,j,w,k;

    ArcNode *p;

    printf("n:");

    scanf("%d",&n); //输入方阵的行列数

    printf("0:No dir"); 

    scanf("%d",&k); //输入是否有向

    for(i=1;i<=n; i++) //初始化方阵对角线为，其余为最大（）

for(j=1; j<=n; j++)

            if(i==j) adjmatrix[i][j]=0;

            else adjmatrix[i][j]=infi;

    do

    { 

        printf("i,j,w:"); 

        scanf("%d%d%d", &i,&j, &w); //输入有直接相连的两节点及其权值

        if(i<1 || i>n || j<1 || j>n)//当i，j 小于或大于n时

            break;                  //退出循环

        adjmatrix[i][j]=w;      //邻接矩阵的i行j列的权值为w

        if(k==0)            //若为无向图

        {  

            adjmatrix[j][i]=w;  //邻接矩阵对称

        }

    }while(1);  //永远

}

void prim(int x) //从顶点x开始

{ 

    int min2tree[N0+1], closest[N0+1],i,j,k; 

    int min;

    for(i=1; i<=n; i++)  //设置所有顶点与开始顶点x相连

        closest[i]=x;

    for(i=1; i<=n; i++)//设置到树的权值为到根x的距离

        min2tree[i]=adjmatrix[x][i]; 

    for(i=1; i<=n-1; i++) //生成树

    { 

        min=infi;

        k=0;

        for(j=1; j<=n; j++) //选择到树的权值最小的边

if( min2tree[j]!=0 && min2tree[j]            { 

                min=min2tree[j];

                k=j;

            }

        min2tree[k]=0;     //将该顶点加入生成树中

for(j=1; j<=n; j++)

//不是自身&&到树的最小权值大于到新添加的生成树的顶点的权值

if( min2tree[j]!=0 && min2tree[j]>adjmatrix[k][j] )

            { 

                min2tree[j]=adjmatrix[k][j];

                closest[j]=k;//顶点j与顶点k相连

             }

    }

    for(i=1; i<=n; i++) //输出生成树

    { 

        j = closest[i]; //j为生成树中与i相连的顶点

        if( i!=j )      //不是自身

printf("(%d->%d)",i,j);

    }

    printf("\\n");

}

void main()

{

  createAdj();

  printf("\\nPrim:");

  prim(1);

  getch();

}

五、调试过程

调试过程及其麻烦，出现过字母错误，逻辑错误，以及语法错误，通过老师和许多同学的帮助最终解决。

六、实验结果

实验截图：

七、总结

    通过本次实验，明白了Prim算法是从连通网中某一个顶点开始，以此作为生成树的初始状态，然后不断地将网中其他顶点添加到生成树上，直到最后一个顶点添加到生成树上时得到最小生成树，其时间复杂度为O(n^2)。而Kruskal算法是一种适用于求稀疏的无向连通网的最小生成树，其时间复杂度主要与网中边的条数e相关为O(eloge)。

附录：

1、宁正元、王秀娟《算法与数据结构》， 北京：清华大学出版社， 2006；

 2、宁正元《数据结构》－用C语言描述，北京：中国水利水电出版社，2000