图的基本操作与kruskal最小生成树实验报告.doc

数据结构实验五 图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验内容问题描述对给定图，实现图的深度优先遍历和广度优先遍历。基本要求以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。【测试数据】由学生依据软件工程的测试技术自己确定。三、实验前的准备工作1、掌握图的相关概念。2、掌握图的逻辑结构和存储结构。3、掌握图的两种遍历算法的实现。四、详细设计建立结构体创建图 END调用greatUDN函数调用BFSTraverse函数输入起始节点名称深度优先遍历输出广度优先遍历输出调用DFSTraverse函数五、源程序#define INFINITY 10000 #define MAX_VERTEX_NUM 40#define MAX 40#include#include#include#includetypedef struct ArCellint adj;ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structchar name20;infotype;typedef structinfotype vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;int LocateVex(MGraph *G,char* v) int c=-1,i;for(i=0;ivexnum;i+)if(strcmp(v,G-)=0)c=i;break;return c;MGraph * CreatUDN(MGraph *G)/初始化图，接受用户输入int i,j,k,w;char v120,v220;printf(请输入图的顶点数,弧数:);scanf(%d%d,&G-vexnum,&G-arcnum);printf(结点名字:n);for(i=0;ivexnum;i+)printf(No.%d:,i+1);scanf(%s,G-);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)G-arcsij.adj=INFINITY;printf(请输入一条边依附的两个顶点和权值:n);for(k=0;karcnum;k+)printf(第%d条边:n,k+1);printf(起始结点:);scanf(%s,v1);printf(结束结点:);scanf(%s,v2);printf(边的权值:);scanf(%d,&w);i=LocateVex(G,v1);j=LocateVex(G,v2);if(i=0&j=0)G-arcsij.adj=w;G-arcsji=G-arcsij;return G;int FirstAdjVex(MGraph *G,int v)int i; if(v=0 &vvexnum) /v合理 for(i=0;ivexnum;i+) if(G-arcsvi.adj!=INFINITY) return i; return -1;void VisitFunc(MGraph *G,int v)printf(%s ,G-);int NextAdjVex(MGraph *G,int v,int w) int k; if(v=0 & vvexnum & w=0 & wvexnum)/v,w合理 for( k=w+1;kvexnum;k+) if(G-arcsvk.adj!=INFINITY) return k; return -1;int visitedMAX;void DFS(MGraph *G,int v)/从第v个顶点出发递归地深度优先遍历图Gint w;visitedv=1;VisitFunc(G,v);/访问第v个结点for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);printf(%d ,G-arcsvw.adj);void DFSTraverse(MGraph *G,char *s)/深度优先遍历int v,k;for(v=0;vvexnum;v+)visitedv=0;k=LocateVex(G,s);if(k=0&kvexnum)for(v=k;v=0;v-)if(!visitedv)DFS(G,v);for(v=k+1;vvexnum;v+)if(!visitedv)DFS(G,v);typedef struct Qnodeint vexnum;struct Qnode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;int InitQueue(LinkQueue *Q)Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode);if(!Q-front)exit(0);Q-front-next=NULL;return 1;void EnQueue(LinkQueue *Q,int a ) QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(0);p-vexnum=a; p-next=NULL;Q-rear-next=p;Q-rear=p;int DeQueue(LinkQueue *Q,int *v) QueuePtr p;if(Q-front=Q-rear)printf(结点不存在!n);exit(0);p=Q-front-next;*v=p-vexnum;Q-front-next=p-next; if(Q-rear=p) Q-front=Q-rear; return *v;int QueueEmpty(LinkQueue *Q)if(Q-rear=Q-front) return 0;return 1;int VisitedMAX;void BFSTraverse(MGraph *G,char *str)/广度优先遍历int w,u,v,k;LinkQueue Q,q;for(v=0;vvexnum;v+) Visitedv=0;InitQueue(&Q);InitQueue(&q);k=LocateVex(G,str);for(v=k;v=0;v-)if(!Visitedv)Visitedv=1; VisitFunc(G,v);EnQueue(&Q,v);/v入队while(!QueueEmpty(&Q) DeQueue(&Q,&u);/出队 for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w) if(!Visitedw) Visitedw=1; VisitFunc(G,v); EnQueue(&Q,w); for(v=k+1;vvexnum;v+)if(!Visitedv)Visitedv=1; VisitFunc(G,v);EnQueue(&Q,v);/v入队while(!QueueEmpty(&Q) DeQueue(&Q,&u);/出队 for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w) if(!Visitedw) Visitedw=1; VisitFunc(G,v); EnQueue(&Q,w); void main()MGraph *G,b;char v10;G=CreatUDN(&b);printf(请输入起始结点名称:);scanf(%s,v);printf(n深度优先遍历:n);DFSTraverse(G,v);printf(n广度优先遍历:n);BFSTraverse(G,v);getch();六、测试数据及调试实验六 图的应用一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、掌握如何应用图解决各种实际问题。二、实验内容本次实验提供2个题目，学生可以任选一个！题目一：最小生成树问题问题描述若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。基本要求1 利用克鲁斯卡尔算法求网的最小生成树。2 要求输出各条边及它们的权值。实现提示通信线路一旦建成，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数。图的存储结构的选取应和所作操作相适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图三、详细设计。存储结构该函数包含三个结构体，即存储顶点、存储边和存储图的结构体，其结构体分别如下所示：1.顶点和边的存储表示用字符串name表示顶点信息，num表示顶点的序号。struct nodechar name10;int num;vex20;用整型begin和end表示边的起点和终点，weight表示边的权值。 typedef struct int begin; int end; int weight;edge;2.图的邻接矩阵存储表示用整型adj表示顶点间的关系，weight表示权值。typedef struct int adj; int weight;AdjMatrixMAXMAX;用arc表示邻接矩阵，vexnum和arcnum表示图当前的顶点数和边数。typedef struct AdjMatrix arc; int vexnum, arcnum;MGraph; 3.2 算法描述该算法是建立一个带权的无向图，并用Kruskal算法求该图的最小生成树，用父结点和子女结点集的形式输出最小生成树。1 无向带权图的建立图的存储结构如上所示，;用adj是否为1判断两顶点间是否有边，adj为1时表示有边，反之没有边，vexnum和arcnum分别表示顶点数和边数，name和num分别表示顶点信息和顶点序号，建图的算法如下所示：void CreatGraph(MGraph *G) int i, j,n,h,m,k; char uMAX,vMAX; printf(请输入边数和顶点数:); scanf(%d %d,&G-arcnum,&G-vexnum) for (i = 1; i vexnum; i+)/初始化图 for ( j = 1; j vexnum; j+) G-arcij.adj = G-arcji.adj = 0; printf(n请输入顶点的信息:); for(n=1;nvexnum;n+) scanf(%s,); vexn.num=n; for ( i = 1; i arcnum; i+) printf(n请输入有边的2个顶点:); scanf(%s,v); scanf(%s,u); for ( k= 1; k vexnum; k+) if(strcmp(v,)=0) m=vexk.num; if(strcmp(u,)=0) h=vexk.num; G-arcmh.adj = G-archm.adj = 1; getchar(); printf(n请输入%s与%s之间的权值:,, ); scanf(%d,&G-arcmh.weight); printf(邻接矩阵为:n); for ( i = 1; i vexnum; i+) for ( j = 1; j vexnum; j+) printf(%d ,G-arcij.adj); printf(n); 2. Kruskal算法克鲁斯卡尔算法：假设连通网N=（V，E），则令最小生成树的起始状态为只有n个顶点而无边的非连通图T=（V，），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有的顶点都在同一连通分量上为止。算法代码如下所示：void MiniSpanTree(MGraph *G) int i, j, n, m; int k = 1; int parentM; edge edgesM; for ( i = 1; i vexnum; i+) for (j = i + 1; j vexnum; j+) if (G-arcij.adj = 1) edgesk.begin = i; edgesk.end = j; edgesk.weight = G-arcij.weight; k+; sort(edges, G); for (i = 1; i arcnum; i+) parenti = 0; printf(最小生成树为:n); for (i = 1; i arcnum; i+) n = Find(parent, edgesi.begin); m = Find(parent, edgesi.end); if (n != m) parentn = m; printf( %dn, , , edgesi.weight); int Find(int *parent, int f) while ( parentf 0) f = parentf; return f;3用起泡法对边权值按从小到大的顺序排列 void sort(edge edges ,MGraph *G) int i, j; int temp; for ( i = 1; i arcnum; i+) for ( j = i+1; j arcnum; j+) if (edgesi.weight edgesj.weight) temp = edgesi.begin; edgesi.begin = edgesj.begin; edgesj.begin = temp; temp = edgesi.end; edgesi.end = edgesj.end; edgesj.end = temp; temp = edgesi.weight; edgesi.weight = edgesj.weight; edgesj.weight = temp; 四、调试4.1 调试过程经过我仔细的调试发现以下三个问题1、问题一：求出图中的最小值 现象：求出的最小值是0原因：图中没有连通的两个顶点之间的权值赋值为02、问题二：求最小生成树时，出现漏洞现象：对某些二叉树能求出最小生成树，但不能普遍适应原因：对于找最小生成树边的各种可能没有考虑全面，代码才没有广泛的适应性3、问题三：两个顶点之间的边是否是最小生成树的边现象：代码的功能不能分辨出是否是最小生成树的边原因：把简单的代码写的很复杂，从而杂乱无章出现错误。4.2程序执行过程1.图4.2.1所示为一10条边6个顶点的无向带权图的顶点间的关系，图4.2.2为输入顶点及边权值的运行情况，图4.2.3为邻接矩阵和最小生成树的输出结果。运行结果：五、源代码#include#include#include#include#define M 20#define MAX 20struct nodechar name10;int num;vex20; typedef struct int begin; int end; int weight;edge;typedef struct int adj; int weight;AdjMatrixMAXMAX;typedef struct AdjMatrix arc; int vexnum, arcnum;MGraph; void CreatGraph(MGraph *);void MiniSpanTree(MGraph *);void sort(edge* ,MGraph *);int Find(int *, int );void CreatGraph(MGraph *G) int i, j,n,h,m,k; char uMAX,vMAX; printf(请输入边数和顶点数:); scanf(%d %d,&G-arcnum,&G-vexnum); for (i = 1; i vexnum; i+)/初始化图 for ( j = 1; j vexnum; j+) G-arcij.adj = G-arcji.adj = 0; printf(n请输入顶点的信息:); for(n=1;nvexnum;n+) scanf(%s,); vexn.num=n; for ( i = 1; i arcnum; i+) printf(n请输入有边的2个顶点:); scanf(%s,v); scanf(%s,u); for ( k= 1; k vexnum; k+) if(strcmp(v,)=0) m=vexk.num; if(strcmp(u,)=0) h=vexk.num; G-arcmh.adj = G-archm.adj = 1; getchar(); printf(n请输入%s与%s之间的权值:,, ); scanf(%d,&G-arcmh.weight); printf(邻接矩阵为:n); for ( i = 1; i vexnum; i+) for ( j = 1; j vexnum; j+) printf(%d ,G-arcij.adj); printf(n); void sort(edge edges ,MGraph *G)/对权值进行排序 int i, j; int temp; for ( i = 1; i arcnum; i+) for ( j = i+1; j arcnum; j+) if (edgesi.weight edgesj.weight) temp = edgesi.begin; edgesi.begin = edgesj.begin; edgesj.begin = temp; temp = edgesi.end; edgesi.end = edgesj.end; edgesj.end = temp; temp = edgesi.weight; ed