图的创建及相关操作.doc

#include #include #define MAX_VERTEX_NUM 10 /*最大顶点数为10*/int visitedMAX_VERTEX_NUM;/*邻接矩阵定义*/typedef struct ArcCell int adj; int *info;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;/*邻接表定义*/*表结点*/typedef struct ArcNodeint adjvex; struct ArcNode *nextarc; ArcNode;/*头结点*/typedef struct VNode char data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arcnum; ALGraph; /*PRIM最小边辅助数组*/ typedef struct ArcInfo char adjvex;int lowcost;ArcInfo,MinEdgeMAX_VERTEX_NUM;/*图的存储* 创建邻接矩阵:CreateMGraph 创建邻接表:CreateALGraph */邻接矩阵/文件读取顶点数、边数、边信息，创建邻接矩阵int CreateMGraph(MGraph &G) int i,j,k;char filename10;int a,b; /用来存储边依附的点v1,v2的位置int w;FILE *fp1;printf(t请输入文件名称:);scanf(%s,filename);if(fp1=fopen(filename,r)=NULL)printf(nt文件打开失败！);return 0;fscanf(fp1,%d,%d,&G.vexnum,&G.arcnum);printf(t已创建的邻接矩阵的结点跟弧的个数：n);printf(t%5d%5dn,G.vexnum,G.arcnum);for(i=0;iG.vexnum;+i) G.vexsi=A+i;for(i=0;iG.vexnum;+i) for(j=0;jG.vexnum;+j)G.arcsij.adj=100; for(k=0;kG.arcnum;+k) fscanf(fp1,%d,%d,%d,&a,&b,&w); G.arcsab.adj=w; G.arcsba=G.arcsab; return 1;fclose(fp1);/输出邻接矩阵void PrintMGraph(MGraph &M)int i,j;printf(t用邻接矩阵表示无向图:n);for(i=0;iM.vexnum;+i)for(j=0;jM.vexnum;+j)if(!j)printf(t);if(M.arcsij.adj!=100)printf(%5d,M.arcsij.adj);elseprintf( 0);printf(n);/邻接表/创建邻接表信息文件int CreateFile2()ALGraph G;FILE *fp;fp=fopen(2.txt,w);int i,j=0,k=0;if(fp=NULL)printf(nt文件打开失败！);return 0;elseprintf(t存储信息，请输入顶点数,边数:);scanf(%d,%d,&G.vexnum,&G.arcnum);printf(%d,%d,G.vexnum,G.arcnum);fprintf(fp,%d,%d,G.vexnum,G.arcnum);/*printf(t请输入各边:n);for(i=0;iG.arcnum;i+)printf(t第%d条边:,i+1);scanf(%d,%d,&j,&k); fprintf(fp,%d,%d,j,k);printf(a);*/printf(t邻接表文件创建成功!);return 1;fclose(fp);/文件读取顶点数、边数、边信息，创建邻接表int CreateALGraph(ALGraph &G) int i,j,k;char filename10; FILE *fp2;ArcNode *s,*s1;printf(nt读取信息，请输入文件名称：nt);scanf(%s,filename);if(fp2=fopen(filename,r)=NULL)printf(t文件打开失败！);return 0;fscanf(fp2,%d,%d,&G.vexnum,&G.arcnum);printf(t已创建的邻接表的结点跟弧的个数：n);printf(t%5d,%5dn,G.vexnum,G.arcnum);for(i=0;iG.vexnum;i+) G.verticesi.data=A+i;G.verticesi.firstarc=NULL; for(k=0;kadjvex=j; s-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=s;s1=(ArcNode *)malloc(sizeof(ArcNode);s1-adjvex=i; s1-nextarc=G.verticesj.firstarc; G.verticesj.firstarc=s1;return 1;fclose(fp2);/*深度优先遍历*/深度优先遍历（邻接表）void DFS(ALGraph G, int v) ArcNode *p;visitedv=1;printf(%5c,G.verticesv.data);/访问第v个顶点for (p=G.verticesv.firstarc;p;p=p-nextarc)if (!visitedp-adjvex) DFS(G, p-adjvex); /对的尚未访问的邻接顶点递归调用void DFSAL(ALGraph G,int vex) /全部遍历int v;for(v=0;vG.vexnum;v+) /访问标志数组初始化visitedv=0; printf(nt遍历结果为：);for(v=0;vG.vexnum;v+) if (!visitedvex)DFS(G,vex); /对v的尚未访问的邻接顶点w调用DFS/深度优先遍历（邻接矩阵）/获取第一个未被访问的邻接节点 int FirstAdjvex(MGraph M,int vex) int w,i; for(i=0;i0&visitedi=0) w=i; break; else w=100; return w; /获取下一个未被访问的邻接节点int NextAdjvex(MGraph M,int w) int t; t=FirstAdjvex(M,w); return t; void visitvex(ALGraph g,int vex) printf(%5c,g.verticesvex.data); /从第v个顶点出发递归地深度优先遍历图Mvoid DFSM(MGraph M,int vex) int w; visitedvex=1; printf(%5c,M.vexsvex); for(w=FirstAdjvex(M,vex);w=0&wM.vexnum;w=NextAdjvex(M,w) if(!visitedw) DFSM(M,w); /对图M作深度优先遍历void DFSMG(MGraph M,int vex) /全部遍历int v;for(v=0;vM.vexnum;v+) /初始化visitedv=0; printf(nt遍历结果为：);for(v=0;vM.vexnum;v+) if (!visitedvex)DFSM(M,vex);/*广度遍历*/BFS辅助队列typedef struct int *base; int front; int rear; Queue; /入队操作enqueue(Queue &q,int e) if(q.rear+1)%MAX_VERTEX_NUM=q.front) printf(The queue is overflow!n); return 0; else q.baseq.rear=e; q.rear=(q.rear+1)%MAX_VERTEX_NUM; return 1; /出队操作dequeue(Queue &q) int t; if(q.front=q.rear) printf(The queue is empty!n); return 0; else t=q.baseq.front; q.front=(q.front+1)%MAX_VERTEX_NUM; return t; /广度优先非递归遍历图（邻接表）void BFSAL(ALGraph g,int i) int j;ArcNode *p;Queue q;q.base=(int *)malloc(MAX_VERTEX_NUM * sizeof(Queue); /构造空队列q.front=0; /队列初始化q.rear=0; for(j=0;jnextarc) if(visitedp-adjvex=0) /w为u的尚未访问的邻接顶点 visitedp-adjvex=1;visitvex(g,p-adjvex); enqueue(q,p-adjvex); /*PRIM算法的最小生成树*/void PRIM(MGraph G,int u) int i,j;int k,temp;MinEdge closedge;k=u;for(j=0;jG.vexnum;j+) /辅助数组初始化if(j!=k)closedgej.adjvex=G.vexsk; closedgej.lowcost=G.arcskj.adj;/adjvex,lowcostclosedgek.lowcost=0; /初始，U=uclosedgek.adjvex=G.vexsk;printf(nt最小生成树的各边为：n);for(i=1;iG.vexnum;i+) /选择其余G.vexnum-1个顶点temp=100;for(j=0;jclosedgej.lowcost&closedgej.lowcost!=0)k=j;temp=closedgej.lowcost; /求出T的下一个结点：第k顶点printf(t%c-%cn,closedgek.adjvex,G.vexsk);closedgek.lowcost=0; /第k顶点并入U集for(j=0;jG.vexnum;j+)if(G.arcskj.adjclosedgej.lowcost)closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj.adj;/main函数void main() int i;ALGraph G;MGraph M;int Button;char ch;dosystem(cls);/界面设计printf(* * * * * 欢 迎 使 用 * * * * *n);printf(* * * * * * * * * * 菜 单* * * * * * * * * * *n);printf(* * 1、 显示该图的邻接矩阵 * *n);printf(* * 2、 显示该图的邻接表 * *n);printf(* * 3、 深度优先遍历(邻接表) * *n);printf(* * 4、 深度优先遍历(邻接矩阵) * *n);printf(* * 5、 广度优先遍历(邻接表) * *n);printf(* * 6、 最小生成树PRIM算法(邻接矩阵) * *n);printf(* * 0、 退出 * *n);printf(* * * * * * * * * * * * * * * * * * * * * * * * * *n);printf(* * * * * * * * * * * * * * * * * * * * * * * * * *n);printf(t请按06按键进行操作：);scanf(%d,&Button);switch(Button) case 1:CreateMGraph(M); PrintMGraph(M);ch=getchar();ch=getchar();break; case 2:/CreateFile2();CreateALGraph(G); ch=getchar();ch=getchar();break; case 3:printf(t请输入遍历位置：);scanf(%d,&i);DFSAL(G,i);ch=getchar();ch=getchar();break; case 4: printf(t请输入遍历位置：);scanf(%d,&i);DFSMG(