图的深度和广度遍历

XXX计算机软件基础课程设计题目：图的深度和广度遍历学院：信息与通信工程学院专业：通信工程专业学生姓名：班级/学号指导老师：起止时间：1XXX本小组的任务是图的深度遍历和广度遍历，根据分配，我做的是图的最小生成树。由于最小生成树软件基础的书上没有具体的程序过程，故而，在课余时间阅读了一些有关算法设计与分析的图书，在此基础上，借鉴了用prim和kruskal算法求解最小生成树的方法，也以此检验自己一学期所学成果，加深对算法设计与分析这门课程的理解，由于所学知识有限，难免有些繁琐和不完善之处，下面简单介绍此程序的设计原理，方法，内容及设计的结果。本程序主要利用数组，for语句的循环，if语句的嵌套，运用以上所学知识编写出的prim和kruskal便可分别输出此图的prim和kruskal算法最小生成树的边的起始位置，终止位置以及权值。2XXX目录1123123XXX二：相关介绍：1、DLL函数（1）原理：动态链接库英文为DLL，是DynamicLinkLibrary的缩写形式，DLL是一个包含可由多个程序同时使用的代码和数据的库，DLL不是可执行文件。动态链接库中定义有两种函数：导出函数(exportfunction)和内部函数(internalfunction)。导出函数可以被其它模块调用，内部函数在定义它们的DLL程序内部使用。动态链接提供了一种方法，使进程可以调用不属于其可执行代码的函数。函数的可执行代码位于一个DLL中，该DLL包含一个或多个已被编译、链接并与使用它们的进程分开存储的函数。DLL还有助于共享数据和资源。多个应用程序可同时访问内存中单个DLL副本的内容。DLL是一个包含可由多个程序同时使用的代码和数据的库。2、最小生成树方法之Kruskal算法（1Kruskal算法是一种按照连通网中边的权值的递增顺序构造最小生成树的算法。将无向图的所有边按权值递增顺序排列，依次选定权值数较小的边，但要求后面选取的边不能与前面选区的边构成回路，若构成回路，则放弃该条边，n个顶点的图中，选取n-1条边即可。注意kruskal算法分n步，其中n是网络中边的数目。按耗费递增的顺序来考虑这n条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。3、最小生成树方法之Prim算法（1）原理：力求从源点到下一个点的距离最短，以此来构建临接矩阵，所以此算法的核心思想是求得源点到下一个点的最短距离。从一个点出发，列出这个点所有邻接的边，选择最小的边，将所连顶点到树中，再到剩余的点中找与这两点（其中之一）距离最小的点加入之中。根据这一指导思想，我把主程序写的简单些，分别调用不同的子函数来实现最小生成树的prim算法。由于要计算权值所4XXXmap[1][2]=map[2][1]=4。先选取一个点作起始点，然后选择它邻近的权值最小的点（如果有多个与其相连的点。如此类推...三：详细设计说明1、编写DLL函数（1）函数：#include"stdafx.h"#include"stdlib.h"extern"C"_declspec(dllimport)intsushu(inti);extern"C"_declspec(dllexport)intsushu(intn){inti;for(i=2;i<n;i++)if(n%i)return1;elsereturn0;}intmain(intargc,char*argv[]){inti=1,m;printf("输入的数字为:");scanf("%d",&m);printf("素数有：\n");while(i+1<=m){i++;if(sushu(i))printf("%d\t",i);}5XXXsystem("pause");return0;}2、最小生成树算法（1）邻接表的存储和建立存储：对于此课题来说，先要建立的就是邻接表，邻接表建立出来才能进行图的遍历和搜索最小生成树。无向图的邻接表对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表。单链表中的每个结点至少包含两个域，一个为邻接点域（adjvex它指示与顶点vi邻接的顶点在图中的位序，另一个为链域（next点vi邻接的下一个结点。为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息与邻接表放在一起来描述图的存储结构。建立：voidinitgraph(algraph&T)//图的初始化函数{printf("输入图结点的个数和弧的个数:");scanf("%d%d",&T.vexnum,&T.arcnum);getchar();T.vertices=(vnode*)malloc(T.vexnum*sizeof(vnode));//开辟vnode类型的空间，将首地址给T.verticesprintf("输入这%d个结点的标识:",T.vexnum);for(inti=0;i<T.vexnum;i++)//输入图结点标识{scanf("%c",&(T.vertices+i)->data);while(''==(T.vertices+i)->data)//屏蔽空格键{scanf("%c",&(T.vertices+i)->data);6XXX}(T.vertices+i)->firstarc=NULL;//将指针置为空}}intlocalvex(algraph&T,charch)//获取图中对应的图标识对应的下标{for(inti=0;i<T.vexnum;i++){if(ch==(T.vertices+i)->data)//找到后就退出{break;}}returni;//返回找到的下标}（2）Kruskal算法：步骤：（1）定义网中的顶点数，网的边数，这里将网的顶点数定为6个，网的边数定为10个。（2）定义一个名为edgeset2的类，其数据成员fromvex,endvex,weight,分别为一条边的起点，终点和权值。（3）定义一个名为tree2的类，定义了一个最小生成树边集的数组，用edgesetge2[e+1]存放网中所有的边，定义一个s2[n+1][n+1]，s为一个集合，一行元素s[i][0]~s[i][n]表示一个集合，若s[i][t]=1。则表示顶点t属于该集合，否则不属于该集合，再定义一个普里姆算法的成员函数kruskal(tree2&t2)。（（4）对kruskal(tree2&t2)函数进行类外定义,定义k并设初值为1用来统计生成树的边数，定义d并设初值为1用来表示待扫描边的下标位置，定义两个7XXX变量m1,m2用来记录一条边的两个顶点所在集合的序号，如果t2.ge2[d].fromvex==j且t2.s2[i][j]==1，则令m1=i，若t2.ge2[d].endvex==j且t2.s2[i][j]==1则令m2=i，最后判断m1是否等于m2，若不等于则令t2.c2[k]=t2.ge2[d]k自加，求出一条边后，合并两个集合，另一个集合设置为空。（5）最后利用for循环键入每条边的起始点，终结点及边上的权值，要求输入的网中的边上的权值必须为从大到小排列，调用kruskal（t）循环输出一条边的起始点，终结点及边上的权值。函数：#include<iostream.h>constintn=6;//网中顶点数constinte=10;//网中边数classedgeset//定义一条生成树的边的类{public:intfromvex;//边的起点intendvex;//边的终点intweight;//边的权值};classedgeset2{public:intfromvex;intendvex;intweight;};classtree2//定义生成树{public:edgesetc2[n];//存放生成树的边edgesetge2[e+1];//存放网中所有边8XXXints2[n+1][n+1];//s为一个集合，一行元素s[i][0]~s[i][n]表示一个集合//若s[i][t]=1。则表示顶点t属于该集合，否则不属于voidkruska(tree2&t2);};voidtree2::kruska(tree2&t2){inti,j;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i==j)t2.s2[i][j]=1;elset2.s2[i][j]=0;intk=1;//统计生成树的边数intd=1;//表示待扫描边的下标位置intm1,m2;//记录一条边的两个顶点所在集合的序号while(k<n){for(i=1;i<=n;i++)for(j=1;j<=n;j++){if((t2.ge2[d].fromvex==j)&&(t2.s2[i][j]==1))m1=i;if((t2.ge2[d].endvex==j)&&(t2.s2[i][j]==1))m2=i;}if(m1!=m2){t2.c2[k]=t2.ge2[d];k++;for(j=1;j<=n;j++){t2.s2[m1][j]=t2.s2[m1][j]||t2.s2[m2][j];//求出一条边后，合并两个集合9XXXt2.s2[m2][j]=0;//另一个集合设置为空}}d++;}}（3）prim算法步骤：（1）定义网中的顶点数，网的边数，这里将网的顶点数定为6个，网的边数定为10个。(2)定义一个名为edgeset类，其数据成员fromvex,endvex,weight,分别为一条边的起点，终点和权值。（3）定义一个名为tree的类，定义了一个最小生成树边集的数组，用数组记录具有最小代价的边，找到后，将该边作为最小生成树的树边保存起来，再定义一个普里姆算法的成员函数prim(tree&t)。（4）对prim(tree&t)函数进行类外定义，分别将顶点数定义为k,边为m,权值为w,定义一个变量min，使其等于32767，即无穷大，利用for循环从顶点1出发求最小生成的数边，即设t.ct[i].fromvex=1。令终止点t.ct[i].endvex=i+1,令t.ct[i].weight=t.s[1][i+1],再利用第二个for循环找到权值最小的树边，从顶点为2开始循环，当j=k-1且小于网中总顶点数时，权值小于无穷则将此权值付给min,并令边m=j。（5）重新修改树边的距离，将原来的边用权值小的边替换，若当前边k小于n(原定边数)，则令tl=t.ct[i].endvex，w=t.s[j][tl]，若w<t.ct[i].weight，则令t.ct[i].weight=w，t.ct[i].fromvex=j。（6）最后利用for循环键入每条边的起始点，终结点及边上的权值。函数：classtree{public:ints[n+1][n+1];//网的邻接矩阵

edgesetct[n+1];//最小生成树的边集

voidprim(tree&t);//普里姆算法

};10XXXvoidtree::prim(tree&t){inti,j,k,min,tl,m,w;//k为当前顶点数,m为当前边数,w为当前权值for(i=1;i<n;i++)//从顶点1出发求最小生成树的边{t.ct[i].fromvex=1;t.ct[i].endvex=i+1;t.ct[i].weight=t.s[1][i+1];}for(k=2;k<=n;k++){min=32767;m=k-1;for(j=k-1;j<n;j++)//找权值最小的树边if(t.ct[j].weight<min){min=t.ct[j].weight;m=j;}edgesettemp=t.ct[k-1];t.ct[k-1]=t.ct[m];t.ct[m]=temp;j=t.ct[k-1].endvex;for(i=k;i<n;i++)//重新修改树边的距离{tl=t.ct[i].endvex;w=t.s[j][tl];if(w<t.ct[i].weight)//原来的边用权值较小的边取代{t.ct[i].weight=w;t.ct[i].fromvex=j;}

}}11XXX}附录：主函数voidmain(){intz;for(z=1;z<=3;z++){cout<<"*************请选择一种算法*****************"<<endl;cout<<"1.prim算法求解最小生成树"<<endl;cout<<"2.kruskal算法求解最小生成树"<<endl;cin>>z;if(z==1){intj,w;treet;cout<<"——prim算法求最小生成树——"<<endl;cout<<"请连续输入网的10条边"<<endl;for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)if(i==j)t.s[i][j]=0;elset.s[i][j]=32767;//i,j）边上无权值，用32767来代替无穷for(intk=1;k<=e;k++)//建立网的邻接矩阵{cout<<"请输入一条边的起始点，终结点及边上的权值：";cin>>i>>j>>w;cout<<endl;t.s[i][j]=w;t.s[j][i]=w;}t.prim(t);//用普里姆算法求最小生成树cout<<":"<<endl;12XXXfor(i=1;i<n;i++)//输出n-1条生成树的边{cout<<t.ct[i].fromvex<<"";cout<<t.ct[i].endvex<<"";cout<<t.ct[i].weight<<endl;}}else{//kruskaltree2t2;cout<<"——kruskal算法求最小生成树——"<<endl;cout<<"请连续输入网的10条边(按权值从小到大的顺序)"<<endl;for(inti=1;i<=e;i++){cout<<"输入一条边的起始边，终止边以及权值:";cin>>t2.ge2[i].fromvex>>t2.ge2[i].endvex>>t2.ge2[i].weigh