数据结构实验报告之图(终极版本)

《数据结构》实验报告姓名系别班级学号实验日期指导教师实验成绩周娟信息学院电子2班102002072012-4-26王政霞实验三图的操作需求分析1>实验目的1.掌握图的基本运算，如创建图、输出图、深度优先遍历、广度优先遍历等。2.掌握最小生成树、最短路径、关键路径等算法。2>实验内容1.编写程序，实现图的遍历。用邻接矩阵或者邻接表描述一个图，图中每个顶点代表一个字符，打印出深度优先搜索和广度优先搜索的节点序列。2.编写程序，输出上图的最小生成树的算法。概要设计1>抽象数据结构类型图的定义:ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R:R={VR}VR={<v,w>|v,w∈V且P（v,w),<v,w>表示从v到w的弧，谓词P（v,w)定义了弧<v,w>的意义或信息}基本操作P：GreatGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DestroyGraph(&G);初始条件：图G存在。操作结果：销毁图G。LocateVex(G,u);初始条件：图G已存在，u和G中的顶点有相同特征。操作结果：将L重置为空表。GetVex(G,v);初始条件：图G存在,v是G中某个顶点。操作结果：返回v的值。PutVex(&G,v,value);初始条件：图G存在，v是G中某个顶点。操作结果：对v赋值value。FirstAdjVex(G,v);初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”。NextAdjVex(G,v,w);初始条件：图G存在，v是G中某个顶点,w是v的邻接顶点。操作结果：返回v的下一个邻接顶点。若w是v的最后一个邻接顶点，则返回“空”。DESTTraverse(G，visit（）)初始条件：图G存在，visit是顶点的应用函数。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数visit一次且仅一次。一旦visit（）失败，则操作失败。}ADTGraph2>各程序模块之间的层次关系图：主程序模块主程序模块链表数据排序模块链表数据排序模块 创建链表模块创建链表模块链表合并模块链表合并模块打印链表模块打印链表模块释放链表模块释放链表模块详细设计#include<stdio.h>#include<iostream>#include<malloc.h>usingnamespacestd;#defineint_max10000#defineinf9999#definemax201.//…………邻接矩阵定义……typedefstructArcCell{intadj;char*info;}ArcCell,AdjMatrix[20][20];typedefstruct{charvexs[20];AdjMatrixarcs;intvexnum,arcnum;}MGraph_L;//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^intlocalvex(MGraph_LG,charv)//返回V的位置{inti=0;while(G.vexs[i]!=v){++i;}returni;}2.创建图用邻接矩阵表示intcreatMGraph_L(MGraph_L&G){charv1,v2;inti,j,w;cout<<"…………创建无向图…………"<<endl<<"请输入图G顶点和弧的个数:"<<endl;cin>>G.vexnum>>G.arcnum;for(i=0;i!=G.vexnum;++i){cout<<"输入顶点"<<i<<endl;cin>>G.vexs[i];}for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j){G.arcs[i][j].adj=int_max;G.arcs[i][j].info=NULL;}for(intk=0;k!=G.arcnum;++k){cout<<"输入一条边依附的顶点和权:"<<endl;cin>>v1>>v2>>w;//输入一条边依附的两点及权值i=localvex(G,v1);//确定顶点V1和V2在图中的位置j=localvex(G,v2);G.arcs[i][j].adj=w;G.arcs[j][i].adj=w;}cout<<"图G邻接矩阵创建成功！"<<endl;returnG.vexnum;}voidljjzprint(MGraph_LG){inti,j;for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j)cout<<G.arcs[i][j].adj<<"";cout<<endl;}}intvisited[max];//访问标记intwe;typedefstructarcnode//弧结点{intadjvex;//该弧指向的顶点的位置structarcnode*nextarc;//弧尾相同的下一条弧char*info;//该弧信息}arcnode;typedefstructvnode//邻接链表顶点头接点{chardata;//结点信息arcnode*firstarc;//指向第一条依附该结点的弧的指针}vnode,adjlist;typedefstruct//图的定义{adjlistvertices[max];intvexnum,arcnum;intkind;}algraph;3.队列定义typedefstructqnode{intdata;structqnode*next;}qnode,*queueptr;typedefstruct{queueptrfront;queueptrrear;}linkqueue;typedefstructacr{intpre;//弧的一结点intbak;//弧另一结点intweight;//弧的权}edg;/4.用邻接表存储图intcreatadj(algraph&gra,MGraph_LG){inti=0,j=0;arcnode*arc,*tem,*p;for(i=0;i!=G.vexnum;++i){gra.vertices[i].data=G.vexs[i];gra.vertices[i].firstarc=NULL;}for(i=0;i!=G.vexnum;++i){for(j=0;j!=G.vexnum;++j){if(gra.vertices[i].firstarc==NULL){if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){arc=(arcnode*)malloc(sizeof(arcnode));arc->adjvex=j;gra.vertices[i].firstarc=arc;arc->nextarc=NULL;p=arc;++j;while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum){tem=(arcnode*)malloc(sizeof(arcnode));tem->adjvex=j;gra.vertices[i].firstarc=tem;tem->nextarc=arc;arc=tem;++j;}--j;}}else{if(G.arcs[i][j].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;/*for(i=0;i!=gra.vexnum;++i){arcnode*p;cout<<i<<"";p=gra.vertices[i].firstarc;while(p!=NULL){cout<<p->adjvex;p=p->nextarc;}cout<<endl;}*/cout<<"图G邻接表创建成功！"<<endl;return1;}voidadjprint(algraphgra){inti;for(i=0;i!=gra.vexnum;++i){arcnode*p;cout<<i<<"";p=gra.vertices[i].firstarc;while(p!=NULL){cout<<p->adjvex;p=p->nextarc;}cout<<endl;}}5.返回依附顶点V的第一个点intfirstadjvex(algraphgra,vnodev)//即以V为尾的第一个结点{if(v.firstarc!=NULL)returnv.firstarc->adjvex;}6.返回依附顶点V的相对于W的下一个顶点intnextadjvex(algraphgra,vnodev,intw){arcnode*p;p=v.firstarc;while(p!=NULL&&p->adjvex!=w){p=p->nextarc;}if(p->adjvex==w&&p->nextarc!=NULL){p=p->nextarc;returnp->adjvex;}if(p->adjvex==w&&p->nextarc==NULL)return-10;}7.始化队列intinitqueue(linkqueue&q)初{q.rear=(queueptr)malloc(sizeof(qnode));q.front=q.rear;if(!q.front)return0;q.front->next=NULL;return1;}intenqueue(linkqueue&q,inte)//入队{queueptrp;p=(queueptr)malloc(sizeof(qnode));if(!p)return0;p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;return1;}intdequeue(linkqueue&q,int&e)//出队{queueptrp;if(q.front==q.rear)return0;p=q.front->next;e=p->data;q.front->next=p->next;if(q.rear==p)q.rear=q.front;free(p);return1;}intqueueempty(linkqueueq)//判断队为空{if(q.front==q.rear)return1;return0;}8.广度优先遍历voidbfstra(algraphgra){inti,e;linkqueueq;for(i=0;i!=gra.vexnum;++i)visited[i]=0;initqueue(q);for(i=0;i!=gra.vexnum;++i)if(!visited[i]){visited[i]=1;cout<<gra.vertices[i].data;enqueue(q,i);while(!queueempty(q)){dequeue(q,e);//cout<<""<<e<<"";for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we)){if(!visited[we]){visited[we]=1;cout<<gra.vertices[we].data;enqueue(q,we);}}}}}intdfs(algraphgra,inti);//声明DFSintdfstra(algraphgra){inti,j;for(i=0;i!=gra.vexnum;++i){visited[i]=0;}for(j=0;j!=gra.vexnum;++j){if(visited[j]==0)dfs(gra,j);}return0;}intdfs(algraphgra,inti){visited[i]=1;intwe1;cout<<gra.vertices[i].data;for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we)){we1=we;if(visited[we]==0)dfs(gra,we);//<<endl;we=we1;}return12;}typedefstruct{intadjvex;intlowcost;}closedge;9./最小生成树PRIM算法intprim(intg[][max],intn){intlowcost[max],prevex[max];//LOWCOST[]存储当前集合U分别到剩余结点的最短路径//prevex[]存储最短路径在U中的结点inti,j,k,min;for(i=2;i<=n;i++)//n个顶点，n-1条边{lowcost[i]=g[1][i];//初始化prevex[i]=1;//顶点未加入到最小生成树中}lowcost[1]=0;//标志顶点1加入U集合for(i=2;i<=n;i++)//形成n-1条边的生成树{min=inf;k=0;for(j=2;j<=n;j++)//寻找满足边的一个顶点在U,另一个顶点在V的最小边if((lowcost[j]<min)&&(lowcost[j]!=0)){min=lowcost[j];k=j;}printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);lowcost[k]=0;//顶点k加入Ufor(j=2;j<=n;j++)//修改由顶点k到其他顶点边的权值if(g[k][j]<lowcost[j]){lowcost[j]=g[k][j];prevex[j]=k;}printf("\n");}return0;}intacrvisited[100];//kruscal弧标记数组intfind(intacrvisited[],intf){while(acrvisited[f]>0)f=acrvisited[f];returnf;}voidkruscal_arc(MGraph_LG,algraphgra){edgedgs[20];inti,j,k=0;for(i=0;i!=G.vexnum;++i)for(j=i;j!=G.vexnum;++j){if(G.arcs[i][j].adj!=10000){edgs[k].pre=i;edgs[k].bak=j;edgs[k].weight=G.arcs[i][j].adj;++k;}}intx,y,m,n;intbuf,edf;for(i=0;i!=gra.arcnum;++i)acrvisited[i]=0;for(j=0;j!=G.arcnum;++j){m=10000;for(i=0;i!=G.arcnum;++i){if(edgs[i].weight<m){m=edgs[i].weight;x=edgs[i].pre;y=edgs[i].bak;n=i;}}//cout<<x<<y<<m;//cout<<endl;buf=find(acrvisited,x);edf=find(acrvisited,y);//cout<<buf<<""<<edf<<endl;edgs[n].weight=10000;if(buf!=edf){acrvisited[buf]=edf;cout<<"("<<x<<","<<y<<")"<<m;cout<<endl;}}}10.主函数voidmain(){algraphgra;MGraph_LG;inti,d,g[20][20];chara='a';d=creatMGraph_L(G);creatadj(gra,G);vnodev; cout<<endl<<"若该图为非强连通图(含有多个连通分量)时"<<endl<<"最小生成树不存在,则显示为非法值。"<<endl<<endl;cout<<"菜单:"<<endl<<endl;cout<<"0、显示该图的邻接矩阵"<<endl;cout<<"1、显示该图的邻接表"<<endl;cout<<"2、深度优先遍历"<<endl;cout<<"3、广度优先遍历"<<endl;cout<<"4、最小生成树PRIM算法"<<endl;cout<<"5、最小生成树KRUSCAL算法"<<endl;ints;chary='y';while(y='y'){cout<<"请选择菜单："<<endl;cin>>s;switch(s){case0:cout<<"邻接矩阵显示如下："<<endl;ljjzprint(G);break;case1:cout<<"邻接表显示如下："<<endl;adjprint(gra);break;case2:cout<<"广度