福建农林大学计算机与信息学院

计算机类

课程设计报告

目        录

1．课程设计的目的…………………………………………………………4

2．课程设计要求……………………………………………………………4

3．算法思想描述……………………………………………………………4

3.1、存储结构的建立……………………………………………………4

3.2、Prim算法……………………………………………………………4

3.3、Kruskal算法…………………………………………………………5

3.4、Dijkstra算法………………………………………………………5

3.5、拓扑排序算法………………………………………………………5

4．程序结构…………………………………………………………………5

5．测试结果…………………………………………………………………6

6．总结………………………………………………………………………7

参考文献………………………………………………………………………8

附录：…………………………………………………………………………9

1.课程设计的目的

此次课程设计的目的是以C语言为基础，通过完成一些具有一定难度的课程设计题目的编写、调试、运行工作，进一步了解并掌握数据结构与算法的设计方法，具备初步的分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；巩固所学理论知识，使理论与实际相结合。从而提高自我分析问题、解决问题的能力。用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风,同时培养学生调查研究、查阅技术文献、资料、手册以及编写技术文献的能力。

2.课程设计要求

图的算法实现

（1）将图的信息建立文件；

 （2）从文件读入图的信息，建立邻接矩阵和邻接表；

        （3）实现Prim、Kruskal、Dijkstra和拓扑排序算法。

3.算法思想描述

       本程序涉及到图的存储结构的建立、Prim、Kruskal、Dijkstra和拓扑排序算法。

3.1、存储结构的建立：

   实现从文件中读入图的信息，同时建立：有向邻接矩阵、无向邻接矩阵、有向邻接表、无向邻接表。

首先进行有向邻接矩阵、邻接表和无向邻接矩阵、邻接表的初始化。

初始化有向邻接矩阵和无向邻接矩阵时，因为不知道会读入几个顶点和几条边，所以取无向邻接矩阵，把它存顶点的字符数组各字符初始化为“*”,以方便判断顶点名称记录到哪了。各边的度都初始化为9999,表示不连通.顶点数和边数都初始为0, GraphKind分别初始为YOUXIANG,WUXIANG。

初始化有向邻接表和无向邻接表时，顶点数、边数、GraphKind初始方法同上. 所有firstarc指向NULL表示还没有边。

接着，向四个图中记录读入边的信息。用一个函数判断新读入的边的顶点是否在以前读入的信息中出现过,若没出现过则去记录顶点名称,出现过则不用了。无向图把信息当作无向的，一次添加两条边，有向图把信息当作有向的，一次只添加一条边，邻接矩阵添加边时，在二维数组对应位置填入边的权，邻接表添加边时，动态申请一个AreNode,加入边的信息后，用头插法插入相应位置。

3.2、Prim算法：

设图中顶点的全集为V, U中存放已选中过的点,用数据结构closedge[]存放选择需要的数据,先把下标0对应点放入U中, closedge[i].uxiabiao=0,(因为U中只有下标0这一个点), closedge[i].lowcost中存放其他点到下标为0的点的权,closedge[0].lowcost=0;表示下标为0的点已在U中了。在closedge按顺序找到最先不在U中,且与U中点直接相连的点,把此边的权赋给min，用擂台式比较法选出closedge[j].lowcost中最小的,此时min中存放的是最小值所在下标,也就是下一个要放入U中的点的下标。输出选中的这条边，它是最小生成树中的一条边。因为U中又加入了一个点，所以要修改closedge[i].lowcost的值，比较新选中点与V-U中点的权和原来的closedge[i].lowcost,取小的那个存入。然后继续如上的选择,循环vexnum-1次,就选出了最小生成树中的vexnum-1条边。

3.3、Kruskal算法：

把有向图g的所有边的信息按权的大小,从小到大存入数据结构Kruskal中。这个排序过程由比较排序实现。创建无向图g,用来存放Kruskal算法生成的最小生成树。从权最小的边开始,看它是否能加入存放最小生成树的g中, selected[20]记录选中过的边中包含的顶点,若该边最多一个顶点出现过,则可以加入,若两个顶点都出现过,则需判断加入该边是否会构成环,从该边一个顶点出发,深度优先搜索到另一顶点,则会构成环。若判断不会构成环，则加入该边。然后继续查看下一条边,直到选完vexnum-1条边。此时g中就存放了最小生成树，把它按打印图的方式打印就可以了。

3.4、Dijkstra算法:

该算法用queue path[]记录定点到其他各点的路径，用数组shuju[]记录算法需要的过程中供选择的数据。先把定点到各点的权存入shuju[]中，再在path[i]中压入定点v和各点i。然后进入for循环vexnum-2次，确定定点到其他vexnum-2个点的路径，确定过程在函数Path()中进行。

   数组visit[]记录顶点到某点路径是否确定过了，在shuju[]中选择一个没选择过的且权最小的点，把该点在visit[]中对应的标记改为1，表示该点选过了，打印出该点对应的queue中的路径，并把该路径存入数组que_min_sub[20]中，方便以后改变其他路径。然后修改shuju[]中的未选过的点的数据，例如对于i点，若刚才选中的点到i点的权+定点到刚才选中的点的权3.5、拓扑排序算法：

该算法首先用数组indegree[]存放每个顶点的入度，count记录输出过的顶点总数，先将入度为0的点放入队列q中，然后进入循环，队列不空时，弹出一个点，count加一，并把与从该点出发直接相连的点的入度减一，如果减的结果是0则压入队列，然后循环，继续从队列中弹出下一个点。若循环结束时，count比顶点总数小，则说明该图中存在环。

    首先对有向图，我们采取邻接表作为数据结构。且将表头指针改为头结点，其数据域存放该结点的入度，入度设为零的结点即没有前趋，至于删除结点及其为尾的弧运算，则可由将这些头顶点的入度减一来实现。

在建立邻接表输入之前，表头向量的每个结点的初始状态为数据域VEX（入度）为零，指针域NXET为空，每输入一条弧< J, K > 建立链表的一个结点，同时令k 的入度加1，因此在输入结束时，表头的两个域分别表示顶点的入度和指向链表的第一个结点指针。

在拓扑排序的过程之中，输入入度为零（即没有前趋）的顶点，同时将该顶点的直接后继的入度减1。

5.1．查邻接表中入度为零的顶点，并进栈。

5.2．当栈为空时，进行拓扑排序。

（1）、退栈，输出栈顶元素V。

（2）、在邻接表中查找Vj的直接后继Vk，将Vk的入度减一，并令入度减至零的顶点进栈。

5.3． 若栈空时输出的顶点数不是N个则说明有向回路，否则拓扑排序结束。为建立存放入度为零的顶点的栈，不需要另分配存储单元，即可借入入度为零的数据域。一方面，入度为零的顶点序号即为表头结点的序号，另一方面，借用入度为零的数据域存放带链栈的指针域（下一个入度的顶点号。 

4.程序结构

本程序的结构如图1所示。其中xiabiao函数用于判断新读入的边的顶点是否在以前读入的信息中出现过,若没出现过则去记录顶点名称,出现过则不用了。Quan_sort函数用于选择权最小的边。cha_ru函数用于将选出的边加入存放最小生成树的图中。y_n_huan函数用来判断加入新的边后，是否会构成环。Path函数用来选择一个点到其余各点中最短的路径，并修改选择后其余各点到U中点的最短路径长度。

图1

图1

5.测试结果

本程序在VC++环境下加以实现，通过实验表明运行正确。下面介绍一个实验示例。 

（1）程序的主菜单,如图2：

图2

（2）图3是用prim算法得到的最小生成树：

图3

（3）图4是用kruskal算法得到的最小生成树，显示的是它的邻接表：

图4

（4）图5是由其中一个点到其他点的最短路径：

图5

（5）图6是该图的拓扑排序序列：

图6

6.总结

图是上学期学习的一个比较复杂的知识点，它包含了丰富的内容。通过课程设计加深了我对图知识的认识，巩固了关于图的一些算法：建立邻接矩阵和邻接表，Prim、Kruskal、Dijkstra和拓扑排序算法。

通过课程设计，有如下几点收获和体会：

1、在上学期的学习中，建立邻接矩阵和邻接表，Prim、、Dijkstra和拓扑排序算法都有详细的讲解，Kruskal算法则只是讲解了大概思想，并没有涉及编程的内容，这就成了整个课程设计中最麻烦的一部分。

在做这部分的时候，我并没有像书中介绍的方法，而是用了一个比较繁琐的方法，重新创建了一个图,用来存放生成的最小生成树。从权最小的边开始,看它是否能加入存放最小生成树的图中, 用一个数组记录选中过的边中包含的顶点,若该边最多一个顶点在数组中出现过,则可以加入,若两个顶点都出现过,则需判断加入该边是否会构成环,方法是从该边一个顶点出发,深度优先搜索到另一顶点,则会构成环，否则不会构成环。这样使程序显得冗长，不过功能还是能完整的实现的。

2、整个程序和以往所编的程序最大的区别就是要求从文件读入信息，文件是C语言中极其重要的部分，通过课程设计，加深了对文件知识的掌握。我的程序原先是只能从固定的一个文件读入图的信息，经过修改，它可以通过输入文件名来选择要读入的文件，使程序更加灵活，功能更加完善。

3、通过课程设计还提高了一点改错能力，对于一些常见问题加深了印象。

每次课程设计都会有多多少少的收获，这些收获将成为以后学习中一笔不可或缺的财富。

参考文献：

[1] 谭浩强. C语言程序设计（第二版）［M］.北京：清华大学出版社，2003

[2] 严蔚敏. 吴伟民. 数据结构（C语言版）［M］.北京：清华大学出版社，2005

[3] 李云清. 杨. 揭安全. 数据结构（C语言版）［M］.北京：人民邮电出版社，2006

[4] 陈慧南. 图书馆目录［832676］  北京：高等教育出版社   2005.130-140.

[5] 宁正元，.               北京：清华大学出版社   2006.53-91.

附录：

参考程序

/*最小生成树*/

#include"stdio.h"/*标准输入输出*/

#include"alloc.h"/*分配空间*/

# define nax 20

#define null 0

/* define link struct type1 */

typedef struct type1{

int vex;

struct type1 *next;

} link;

/* {

int vex;

link naxt;

};

*/

#define len sizeof(link)

#define NULL 0

 link *al[nax+1];

 int n,e;

 link *p;

 int store[nax+1];

 void readlist()

 {

 int i,j,k;

 link *q;

 printf("请输入结点数目N=\\n");

 scanf("\\n%d",&n);

 printf("请输入有向图的关联对数E=?\\n");

 scanf("\\n%d",&e);

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

  {

  al[i]=(link *)malloc(len);

al[i]->vex=0;

al[i]->next=NULL;

  }

 for(i=1;i<=e;i++)

  {

  printf("输入第%d对关联对\\n",i);

  scanf("\\n%d,%d",&j,&k);

  al[k]->vex=al[k]->vex+1;

  q=(link *)malloc(len);

q->vex=k;

q->next=al[j]->next;

al[j]->next=q;

  }

 }

 void topo()

 {

 int i,j,k,top;

 link *q;

 top=0;

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

  {

  if(al[i]->vex==0)

    {

al[i]->vex=top;

    top=i;

    }

  }

 i=0;

 while(top)

  {

  j=top;

top=al[top]->vex;

  i=i+1;

  store[i]=j;

q=al[j]->next;

  while(q)

    {

k=q->vex;

    al[k]->vex=al[k]->vex-1;

    if(al[k]->vex==0)

      {

al[k]->vex=top;

      top=k;

      }

q=q->next;

    }

  }

 if(i else

  {

  printf("拓扑序列为：");

  for(i=1;i<=n;i++) printf("%5d",store[i]);

  }

 }

/*dijkstra 算法*/

void Dijkstra(int x)

{

    int mark[n0+1],dist[n0+1],path[n0+1];

    int i,j,k;

    int min;

    for(i=1;i<=n;i++)                               //为数组赋初值

       {

          mark[i]=2;

          dist[i]=mapmatrix[x][i];

          path[i]=x;

       }

    mark[x]=1;          //找到第二组中找到离原点最近的节点，把其下标给k

   for(i=2;i<=n;i++)

    { min=32767;

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

       {

          if(mark[j]==2&&dist[j] //若是第二组中的并且该值小于min保存该节点的小标

            {

               min=dist[j];          //  把该值赋给min

               k=j;                 // 记录该值的小标

            }

       }

     mark[k]=1;

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

  //重新计算第二组中离原点最近的距离，看是否小于原值

       {

          if(mark[j]==2&&dist[j]>(double)dist[k]+(double)mapmatrix[k][j])

             {

                dist[j]=dist[k]+mapmatrix[k][j];

                path[j]=k;

             }

       }      //将k保存在path中作为原点到该节点的路径的倒数第二个节点

    }

   for(i=1; i<=n; i++)                    //按path中的记录输出最短路径

     if(i!=x)

       { printf("%d:%d",dist[i],i);    // 输出该节点值与该节点的名

         j=i;

         while(j!=x)                // 当不为起点时做

            {  j=path[j];        //将j赋值为从原点到j的到数第个节点

               printf("<-%d",j);     // 输出j

            }

        printf("\\n");

       }

}

 void main()

 {  readlist();

  topo();

   createmap();                //创建图的函数

   printmapmatrix();           //使用邻接表输出

   dfs(1);                     //深度优先遍历

   printf("\\n");

   bfs(1);                      //广度优先遍历

   printf("\\n");

   Dijkstra(1);                //Dijkstra算法

   getch();

 }