《图的基本操作与kruskal最小生成树实验报告.doc》由会员分享，可在线阅读，更多相关《图的基本操作与kruskal最小生成树实验报告.doc（22页珍藏版）》请在金锄头文库上搜索。
1、 数据结构实验五 图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验内容问题描述对给定图，实现图的深度优先遍历和广度优先遍历。基本要求以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。【测试数据】由学生依据软件工程的测试技术自己确定。三、实验前的准备工作1、掌握图的相关概念。2、掌握图的逻辑结构和存储结构。3、掌握图的两种遍历算法的实现。四、详细设计建立结构体创建图 END调用greatUDN函数调用BFSTraverse函数输入起始节点名称深度优
2、先遍历输出广度优先遍历输出调用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 vex
3、num,arcnum;MGraph;int LocateVex(MGraph *G,char* v) int c=-1,i;for(i=0;ivexnum;i+)if(strcmp(v,G-vexsi.name)=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)
4、;scanf(%s,G-vexsi.name);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-arcsj
5、i=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-vexsv.name);int NextAdjVex(MGraph *G,int v,int w) int k; if(v=0 & vvexnum & w=0 & wvexnum)/v,w合理 for( k=w+1;
6、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,
7、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-
8、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);
9、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(
10、&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
11、);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);BFST
12、raverse(G,v);getch();六、测试数据及调试实验六 图的应用一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、掌握如何应用图解决各种实际问题。二、实验内容本次实验提供2个题目，学生可以任选一个！题目一：最小生成树问题问题描述若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。基本要求1 利用克鲁斯卡尔算法求网的最小生成树。2 要求输出各条边及它们的权值。实现提示通信线路一旦建成，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数。图的存储结构的选取应和所作操作相适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图三、详细设计。存储结构该函数包含三个结构体，即存储顶点、存储边和存储图的结构体，其结构体分别如下所示：1.顶点和边的存储表示用字符串name
