数据结构实验报告邻接矩阵.doc

数据结构实验报告-邻接矩阵#include #define maxvertexnum 100/设置邻接矩阵的最大阶数#define queuesize 100/设置循环队列的最大空间#define MAXVER 10#define INFININTY 1000000typedef int ARRMAXVER;typedef structint front,rear,count,dataqueuesize;cirqueue;/循环队列结构定义typedef int vertextype;/设置图的顶点信息为整型typedef int edgetype;/设置边上权值为整型typedef structvertextype vexsmaxvertexnum;/图的顶点信息表edgetype edgesmaxvertexnummaxvertexnum;/图的邻接矩阵int n,e;/图的顶点数和边数mgraph;/图的邻接矩阵表示结构定义typedef enumFALSE,TRUEboolean;boolean visitedmaxvertexnum;/顶点访问标记向量typedef struct nodeint adjvex;/存放邻接点序号int data;struct node *next;/指向下一个边结点edgenode;/图的邻接表的边结点定义typedef struct vnodevertextype vertex;/顶点数据域edgenode *firstedge;/指向第一个边结点vertexnode;/图的邻接表表示的顶点结点定义typedef vertexnode adjlistmaxvertexnum;/用向量定义图的邻接表表示的顶点表typedef structadjlist adjlist;int n;/图的顶点数int e;/图的边数algraph;/定义图的邻接表typedef structint vexsMAXVER;int arcsMAXVERMAXVER;int vexnum,arcnum;Mgraph;main()/主函数 int i,mm,nn,j; /*建立用邻接矩阵表示的图，并进行深度优先搜索和广度优先搜索 */mgraph *g;algraph *alg;algraph p;mgraph q;Mgraph M_Dijstra;g=(mgraph*)malloc(sizeof(mgraph);/申请图g的邻接矩阵表示空间alg=(algraph*)malloc(sizeof(algraph);/申请图g的邻接矩阵表示空间printf(/*交通网中的最短路径，请输入功能代码*n);printf(/ 1，显示网图 *n);printf(/ 2，显示邻接表 *n);printf(/ 3，网图的深度和广度搜索 *n);printf(/ 4，prim算法建立最小生成树 *n);printf(/ 5，任意两个城市之间的最短路径 *n);printf(/*计算机03-3 20号，21号，22号，23号*n);scanf(%d,&i);switch(i)case 1 : createmgraph(g); printf(n网图显示：n); ShowMgraph(g) ; break;case 2 : createalgraph(alg); p =*alg; printf(n邻接图显示：n); ShowALgraph(p); break;case 3 : createmgraph(g); printf(广度优先搜索:n); bfstraverse(g); printf(深度优先搜索:n); dfstraverse(g); break;case 4 :printf(请先输入城市间的路径信息：);createmgraph_Dijstra(g);q = *g;M_Dijstra.vexnum = q.n;M_Dijstra.arcnum = q.e;for(i=1;i=q.n;i+)for(j=1;j=q.n;j+) M_Dijstra.arcsij = q.edgesij; Dijstra(M_Dijstra,1);/Dijkstra(q);printf(执行完毕！);break;/createmgraph(g);/建立图g/printf(the bfs is:);/对图g进行广度优先搜索/bfstraverse(g);void Dijstra(Mgraph N,int s) /*S 为源点编号，有向图 N 用邻接矩阵表示*/ARR dist,pred,mark; /* distk数组存储的是当前所知的从源点s到终点k的最短路径*；求解结束时diskk存储源点s到终点k的最短路径*/*predk数组在求解过程中存储的是当前所知的从源点到终点的当前路径上顶点的直接前驱顶点编号，求解结束时候predk存储源点到终点的路径上的直接前驱顶点编号/*markk表示从源点到终点的最短路径是否求得*/int i,u,k,min;for(k=1;k0&distkINFININTY)predk=s; /如果distk满足上面条件，说明源节点s是k的路径上的前驱elsepredk=0;markk=0;/*end for*/marks=1; /初始化完毕，marks=1，表示s已经被我们决策过for(i=1;i=N.vexnum;i+) /逐条确定最短路径min=INFININTY;for(k=1;k=N.vexnum;k+)if(markk=0&distkmin)/表示满足条件是： markk=0表示这个节点还没有被决策过min=distk;u=k; /通过这个循环得到没有被决策过的distk最小的节点/*end if*/marku=1; /得到之后标记这个节点为已经被决策过for(k=1;k=N.vexnum;k+)if(markk=0)&(distu+N.arcsukdistk) /如果从源点到的距离大于通过中转的路径，则进行下面的转换distk=distu+N.arcsuk;predk=u; /*end if*/ /*end 外层for*/for(i=1;i=N.vexnum;i+) /输出每条最短路径及其长度信息if(i!=s)&(distiINFININTY)k=i;printf(shortest path:);while(k!=s)printf(%dn,&g-e);/输入图g的顶点数和边数printf(请输入顶点信息:n);for(i=1;in;i+)/构造一个只含n个顶点，边数为0的图scanf(%d,&(g-adjlisti.vertex);/输入顶点的数据域（为了简单起见，输入为整数）g-adjlisti.firstedge=NULL;/将顶点结点的firstedge域置为空/end forfor(k=1;ke;k+)printf(输入边的信息，依次输入首尾节点和权:n);scanf(%d%d%d,&i,&j,&t);/输入对应于一条边的顶点序号序偶对，要求顶点序号为0n-1s=(edgenode *)malloc(sizeof(edgenode);/申请一个边结点*ss-adjvex=j;/将序号j放入边结点*s的adjvex域s-data = t;s-next=g-adjlisti.firstedge;/将边结点*s作为第一个邻接点插入到序号为i的顶点的边表中g-adjlisti.firstedge=s;if (flag)/若要建立无向图s=(edgenode *)malloc(sizeof(edgenode);/申请一个边结点*ss-adjvex=i;/将序号i放入边结点*s的adjvex域s-data = t;s-next=g-adjlistj.firstedge;/将边结点*s作为第一个邻接点插入到序号为j的顶点的边表中g-adjlistj.firstedge=s;/end of if/end of for/end of creatalgraph/显示邻接表void ShowALgraph(algraph G)int i;edgenode *p;for(i=1;i); if(G.adjlisti.firstedge!=NULL) p = G.adjlisti.firstedge; while(p!=NULL) printf(%d%d,p-adjvex,p-data); printf(-); p= p-next; printf(n); /这个程序创建一个邻接矩阵，满足dijdstra的要求！createmgraph_Dijstra(mgraph *g)int i,j,k,w;int flag;printf(n创建一个网图:n);printf(有向图请输入0n);printf(无向图请输入1n);scanf(%d,&flag);printf(input n,en);scanf(%d%d,&g-n,&g-e);/输入图*g的顶点数和边数printf(input nodes:n);for(i=1;in;i+)/输入n个顶点的信息scanf(%d,&(g-vexsi);for(i=1;in;i+)/将邻接矩阵数组初始化for(j=1;jn;j+)g-edgesij=INFININTY;for(i=1;in;i+)/将对角线的置零for(j=1;jn;j+)if(i=j) g-edgesij=0;for(k=1;ke;k+)/读入n有向边对应的三元组(i,j,w),若构造有向图，/i为有向边的弧尾，j是有向边的弧头，/w是有向边的权值（建立一般的有向图时，可输入1）printf(input i,j,w:n);scanf(%d%d%d,&i,&j,&w);g-edgesij=w;if (flag)/构造无向图g-edgesji=w;/建立图g的邻接矩阵表示 没有联系的节点之间用0表示，但是不符合dijdstra方法要求，所以另外写一个方法createmgraph(mgraph *g)int i,j,k,w;int flag;printf(n创建一个网图:n);printf(有向图请输入0n);printf(无向图请输入1n);scanf(%d,&flag);printf(input n,en);scanf(%d%d,&g-n,&g-e);/输入图*g的顶点数和边数printf(input nodes:n);for(i=1;in;i+)/输入n个顶点的信息scanf(%d,&(g-vexsi);for(i=1;in;i+)/将邻接矩阵数组初始化for(j=1;jn;j+)g-edgesij=0;for(k=1;ke;k+)/读入n有向边对应的三元组(i,j,w),若构造有向图，/i为有向边的弧尾，j是有向边的弧头，/w是有向边的权值（建立一般的有向图时，可输入1）printf(input i,j,w:n);scanf(%d%d%d,&i,&j,&w);g-edgesij=w;if (flag)/构造无向图g-edgesji=w;/显示邻接矩阵void ShowMgraph(mgraph *g)int i,j; for (i=1;in;i+) printf(第%d行,i); for(j=1;jn;j+) printf(%d,g-edgesij); printf(n); bfsm(mgraph *g,int k)/对以邻接矩阵表示的图，以序号为k的顶点作为出发点进行广度优先搜索int i,j;cirqueue *q;q=(cirqueue *)malloc(sizeof(cirqueue);/申请循环队列空间*qq-rear=q-front=q-count;/将循环队列*q设置为空队列printf(visit vertex:%d ,g-vexsk);/访问序号为k的顶点visitedk=TRUE;/将序号为k是结点设置为已访问过q-dataq-rear=k;q-rear=(q-rear+1)%queuesize;q-count+;/将序号为k的顶点入队while(q-count)/若队列不为空，则做以下操作i=q-dataq-front;q-front=(q-front+1)%queuesize;q-count-;/将队首元素(序号为i的顶点)出队for(j=1;jn;j+)/寻找序号为i顶点的邻接点，并做如下处理if(g-edgesij!=0)&(!visitedj)/若序号为i的顶点有未访问过邻接点printf(visit vertex:%d ,g-vexsj);/访问序号为j的顶点visitedj=TRUE;/设置序号为j的顶点访问过标记q-dataq-rear=j;q-rear=(q-rear+1)%queuesize;q-count+;/将序号为j的顶点入队/end of if/end of for/end of bfsmbfstraverse(mgraph *g)/对以邻接矩阵表示的图，进行广度优先搜索int i;for(i=1;in;i+)/将所有顶点设置为未访问过visitedi=FALSE;for(i=1;in;i+)/对邻接矩阵表示的图进行广度优先搜索if(!visitedi)bfsm(g,i);printf(n);/end of bfstraversedfsm(mgraph *g,int i)/对以邻接矩阵表示的图，以序号为i的顶点为出发点进行深度优先搜索int j;printf(visit vertex:%d ,g-vexsi);/访问序号为i的顶点visitedi=TRUE;/将序号为i的顶点设置访问过标记for(j=1;jn;j+)/扫描邻接矩阵的第i行，做以下操作if (g-edgesij!=0)&(!visitedj)/寻找序号为i的顶点的未访问过的邻接点(设序号为k),dfsm(g,j);/以序号为k的顶点为出发点进行深度优先搜索/end of dfsmdfstraverse(mgraph *g)/对以邻接矩阵表示的图，进行深度优先搜索int i;for(i=1;in;i+)/将图的所有顶点设置为未访问过visitedi=FALSE;for(i=1;in;i+)/对图*g进行深度优先搜索if(!visitedi)dfsm(g,i);printf(n);/end of dfstraverse