图的遍历和生成树

.西安交通大学数据结构 课程设计课程名称： 图的遍历和生成树求解实现学 院： 信息科学学院班 级： 计算机科学（1）班设 计 者： 李想学 号： 200805693210.设计时间： 2010-06-22 目 录第一章 需求分析2第二章 详细设计3第三章 源程序11第四章 运行结果及调试分析19第五章 使用说明.22第六章 课设体会及总结22参考文献22第一章：需求分析1：设计要求：(1) 先任意创建一个图；(2) 图的DFS,BFS的递归和非递归算法的实现(3) 最小生成树（两个算法）的实现，求连通分量的实现(4) 要求用邻接矩阵、邻接表、十字链表等多种结构存储实现2：所作题目的意义：图是一种较线性表和树更为复杂的数据结构。在图形结构中结点的关系可以是任意的，图中任意两个数据元素之间都可能相关，因此，图的应用极为广泛，特别是近几年来的迅速发展，已深入到诸如语言学、逻辑学、物理、化学、计算机科学以及数学的其他分支中。图的遍历通常有两条路径：深度优先搜索和广度优先搜索。此次课程设计，可以让我对图这个概念有进一步的了解。 3：本人所做的工作： 和小组成员一起完成本次程序的编写，查过大量关于这方面的资料。经过多次的修改和调试后，终于把程序运行了出来。至于文档是自己独立完成的。4：系统的主要功能： 先创建一个图，用两种搜索方式实现图的遍历，并求得图的最小生成树以及连通分量，用多种存储结构实现。第二章：详细设计定义九个结构体变量: arc algraphArcCellarcnodeclosedgelinkqueueMgraph_Lqnodevnode主要的函数：void main()int localvex(MGraph_L G,char v)int creatMGraph_L(MGraph_L &G)void ljjzprint(MGraph_L G)int creatadj(algraph &gra,MGraph_L G)void adjprint(algraph gra)int firstadjvex(algraph gra,vnode v)int nextadjvex(algraph gra,vnode v,int w)int initqueue(linkqueue &q)int enqueue(linkqueue &q,int e)int dequeue(linkqueue &q,int &e)int queueempty(linkqueue q)void bfstra(algraph gra)int dfstra(algraph gra)int dfs(algraph gra,int i)int bfstra_fen(algraph gra)int minispantree(MGraph_L G,char u)int minimum(closedge *p)int prim(int cmax,int n)int find(int acrvisited,int f)void kruscal_arc(MGraph_L G,algraph gra)void main()主函数主要是调用各个函数，显示菜单如下：0、显示该图的邻接矩阵; 1、显示该图的邻接表2、广度优先遍历 3、深度优先遍历4、最小生成树PRIM算法5、最小生成树KRUSCAL算法 6、该图的连通分量 7、退出程序用户输入自己的选择，就可以对图进行各种运算了break;cout邻接矩阵显示如下：endl;IF Multis=1s=0cout选择菜单：endl;y=yalgraphgra;int creatMGraph_L(MGraph_L &G)G.arcsij.adj=int_max;MultiFOR +jj!=G.vexnumj=0cout输入顶点i+1endl;+ii!=G.vexnumi=0+ii!=G.vexnumi=0charv1,v2; 创建一个无向图，用邻接矩阵表示。先输入图G顶点和边的个数，再输入一条边依附的顶点和权，然后图G邻接矩阵创建成功 在此函数中调用了int localvex(MGraph_L G,char v)函数，确定顶点在图中的具体位置 用两个数组分别存储数据元素的信息和数据元素之间的关系的信息。 void bfstra(algraph gra) Multi!visitedi+ii!=gra.vexnumi=0initqueue(q);visitedi=0;+ii!=gra.vexnumi=0inti,e; 广度优先遍历：按广度优先非递归遍历图G，使用辅助队列q和访问标志数组visited. 其中关于队列q，调用了函数int initqueue(linkqueue &q) ：初始化队列int enqueue(linkqueue &q,int e) 入队int dequeue(linkqueue &q,int &e) 出队int queueempty(linkqueue q) 判断队为空标志数组 int visitedmax调用函数：int firstadjvex(algraph gra,vnode v) 返回依附顶点V的第一个点 即以V为尾的第一个结点int nextadjvex(algraph gra,vnode v,int w) 返回依附顶点V的相对于W的下一个顶点 int dfstra(algraph gra)int dfs(algraph gra,int i) 深度优先遍历：对图G作深度优先遍历，使用全局变量，使该算法不必设函数指针参数访问标志数组初始化，从第J个顶点出发递归地深度优先遍历图G，对J的尚未访问的邻接顶点WE递归调用该算法IF visitedi=0;return0;+jj!=gra.vexnumj=0+ii!=gra.vexnumi=0inti,j;int minispantree(MGraph_L G,char u)Multiclosedge_aj.adjvex=u;+ii!=G.vexnumi=1j!=kreturn0;+jj!=G.vexnumj=0intk,j,i; 构造最小生成树： 用prim算法从 第u个顶点出发 构造图G的最小生 成树T，输出T 的各条边，记录从顶 点u到v-u的代 价最小的边的 辅助数组，并初始化 辅助数组。初始时为 U=u，再选择其余 G.vexnum-1个顶点，求出 T的下一个结点，第k顶点。 输出生成树的边，第 k顶点并入 U集，等新顶点 并入U后重新选 择最小边。int prim(int cmax,int n)MultiMultii+i=ni=2lowcosti=c1i;closest1=0;i+i=ni=2inti,j,k,min,lowcostmax,closestmax; Prim算法： 找最小的边 设立数组 closesti，其每一个元素 包含两个分量， 一 个分量为closetv.vert,存 放生成树中某一顶点u的 编号，该顶点与生成树外 的顶点v的距离，比生成 树中其他顶点到v的距 离都小。这个距离为v 到生成树的最短距离。 另一个分量为 closeti.cost，记录了 上述两顶点间边的代价， 即v到生成树的距离。void kruscal_arc(MGraph_L G,algraph gra)acrvisitedi=0;IF FOR +ii!=gra.arcnumi=0intx,y,m,n;+jj!=G.vexnumj=i+ii!=G.vexnumi=0edgedgs20; kruscal算法： 按边权值递增的次序 来构造最小代价生成树 初始状态： 由图G的n个 孤立点和空的生成树的 边集构成 生成步骤： 每次从图的边集中选 取权位最小的边，并 标记该边 kruscal弧标记数 组int acrvisited100 调用 int find(int acrvisited,int f) 函数，来寻找权值最小的边第三章：源程序#include #include using namespace std;#include #define int_max 0#define inf 9999 #define max 20 #define MAXCOST 1000 /顶点个数的最大值 /邻接矩阵定义 typedef struct ArcCellint adj; /边的权值 char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20;AdjMatrix arcs;int vexnum,arcnum;MGraph_L;/int localvex(MGraph_L G,char v)/返回V的位置int i=0;while(G.vexsi!=v)+i;return i;int creatMGraph_L(MGraph_L &G)/创建图用邻接矩阵表示char v1,v2;int i,j,w;cout创建无向图endl请输入图G顶点和边的个数:G.vexnumG.arcnum;for(i=0;i!=G.vexnum;+i)cout输入顶点i+1G.vexsi;for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j) G.arcsij.adj=int_max;G.=NULL;for(int k=0;k!=G.arcnum;+k) cout输入一条边依附的顶点和权:v1v2w;/输入一条边依附的两点及权值i=localvex(G,v1);/确定顶点V1和V2在图中的位置j=localvex(G,v2);G.arcsij.adj=w;G.arcsji.adj=w;cout图G邻接矩阵创建成功！endl;return G.vexnum;void ljjzprint(MGraph_L G)int i,j;for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)coutG.arcsij.adj ;coutadjvex=j;gra.verticesi.firstarc=arc;arc-nextarc=NULL;p=arc;+j;while(G.arcsij.adj!=int_max&j!=G.vexnum)tem=(arcnode *)malloc(sizeof(arcnode);tem-adjvex=j; gra.verticesi.firstarc=tem;tem-nextarc=arc;arc=tem;+j;-j;elseif(G.arcsij.adj!=int_max&j!=G.vexnum)arc=(arcnode *)malloc(sizeof(arcnode);arc-adjvex=j;p-nextarc=arc;arc-nextarc=NULL;p=arc;gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;cout图G邻接表创建成功！endl;return 1; void adjprint(algraph gra) int i;for(i=0;i!=gra.vexnum;+i)arcnode *p;couti ;p=gra.verticesi.firstarc;while(p!=NULL)coutadjvexnextarc;coutadjvex;int nextadjvex(algraph gra,vnode v,int w)/返回依附顶点V的相对于W的下一个顶点arcnode *p;p=v.firstarc;while(p!=NULL&p-adjvex!=w)p=p-nextarc;if(p-adjvex=w&p-nextarc!=NULL)p=p-nextarc;return p-adjvex;if(p-adjvex=w&p-nextarc=NULL)return -10;int initqueue(linkqueue &q)/初始化队列q.rear=(queueptr)malloc(sizeof(qnode);q.front=q.rear;if(!q.front)return 0;q.front-next=NULL;return 1;int enqueue(linkqueue &q,int e)/入队queueptr p;p=(queueptr)malloc(sizeof(qnode);if(!p)return 0;p-data=e;p-next=NULL;q.rear-next=p;q.rear=p;return 1;int dequeue(linkqueue &q,int &e)/出队queueptr p;if(q.front=q.rear)return 0;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear=p)q.rear=q.front;free(p);return 1;int queueempty(linkqueue q)/判断队为空if(q.front=q.rear)return 1;return 0;void bfstra(algraph gra)/广度优先遍历int i,e;linkqueue q;for(i=0;i!=gra.vexnum;+i)visitedi=0;initqueue(q);for(i=0;i!=gra.vexnum;+i)if(!visitedi) visitedi=1;coutgra.verticesi.data=0;we=nextadjvex(gra,gra.verticese,we)if(!visitedwe)visitedwe=1;coutgra.verticeswe.data ;enqueue(q,we);int dfs(algraph gra,int i);/声明DFSint dfstra(algraph gra) /深度优先遍历 int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)dfs(gra,j);return 0;int dfs(algraph gra,int i)visitedi=1;int we1;coutgra.verticesi.data=0;we=nextadjvex(gra,gra.verticesi,we)we1=we;if(visitedwe=0)dfs(gra,we);we=we1; return 12;int bfstra_fen(algraph gra)/求连通分量int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)dfs(gra,j);coutendl; return 0;typedef struct int adjvex;int lowcost;closedge;int minimum(closedge *p);int minispantree(MGraph_L G,char u)int k,j,i;closedge closedge_a20;k=localvex(G,u);coutkendl;for(j=0;j!=G.vexnum;+j)if(j!=k) closedge_aj.adjvex=u;closedge_aj.lowcost=G.arcskj.adj;for(i=1;i!=G.vexnum;+i)k=minimum(closedge_a);coutk;coutclosedge_ak.adjvex G.vexskendl;closedge_ak.lowcost=0;for(j=0;j!=G.vexnum;+j)if(G.arcskj.adjp-lowcost)s=p-lowcost;return s;int prim(int cmax,int n) /最小生成树PRIM算法int i,j,k,min,lowcostmax,closestmax; for (i=2;i=n;i+) /*从顶点1开始*/ lowcosti=c1i; closesti=1; closest1=0; for (i=2;i=n;i+) /*从U之外求离U中某一顶点最近的顶点*/ min=MAXCOST; j=1; k=i; while (j=n) if (lowcostjmin & closestj!=0) min=lowcostj; k=j; j+; cout(closestk,k) ; /*打印边*/ closestk=0; /* k假如到U中 */ for (j=2;j=n;j+) if (closestj!=0 & ckjlowcostj) lowcostj=ckj; closestj=k; cout0)f=acrvisitedf;return f;void kruscal_arc(MGraph_L G,algraph gra) edg edgs20;int i,j,k=0;for(i=0;i!=G.vexnum;+i)for(j=i;j!=G.vexnum;+j)if(G.arcsij.adj!=10000)edgsk.pre=i;edgsk.bak=j;edgsk.weight=G.arcsij.adj;+k;int x,y,m,n;int buf,edf;for(i=0;i!=gra.arcnum;+i)acrvisitedi=0; for(j=0;j!=G.arcnum;+j)m=10000;for(i=0;i!=G.arcnum;+i)if(edgsi.weightm)m=edgsi.weight;x=edgsi.pre;y=edgsi.bak;n=i;buf=find(acrvisited,x);edf=find(acrvisited,y); edgsn.weight=10000;if(buf!=edf)acrvisitedbuf=edf;cout(x,y)m;void main() algraph gra;MGraph_L G;int i,d,g2020;char a=a;d=creatMGraph_L(G);creatadj(gra,G);vnode v;coutendl注意：若该图为非强连通图时endl 最小生成树不存在,则显示为非法值。endlendl;cout菜单endlendl;cout0、显示该图的邻接矩阵endl;cout1、显示该图的邻接表endl;cout2、广度优先遍历endl;cout3、深度优先遍历endl;cout4、最小生成树PRIM算法endl;cout5、最小生成树KRUSCAL算法endl;cout6、该图的连通分量endl;cout7、退出程序endl;int s;char y=y;while(y=y)cout选择菜单：s;switch(s)case 0:cout邻接矩阵显示如下：endl;ljjzprint(G); break;case 1:cout邻接表显示如下：endl;adjprint(gra); break;case 2:cout广度优先遍历：;bfstra(gra);coutendl; break;case 3:for(i=0;i!=gra.vexnum;+i)visitedi=0;cout深度优先遍历：; dfstra(gra);coutendl; break;case 4:for(i=0;i!=G.vexnum;+i)for(int j=0;j!=G.vexnum;+j)gi+1j+1=G.arcsij.adj;coutprim:endl最小生成树边集为：;prim(g,d); break;case 5:coutkruscal:endl;kruscal_arc(G,gra); break;case 6:cout连通分量:;bfstra_fen(gra); break;case 7:exit(0); break;default:coutendly;if(y=n) break;第四章 运行结果及调试分析所要建的图为： 1A B2 4 6C D 5运行结果 创建一个图：显示菜单：选择0，输出邻接矩阵：选择1，输出邻接表：选择2，广度优先遍历：选择3，深度优先遍历：选择4