数据结构 图的建立

《数据结构 图的建立》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、戴瑞贤计算机13-5班20131401702实验十　图的建立实验目的：1)理解图的基本概念，掌握用邻接矩阵和邻接表的方法描述图的存储结构。实验内容：1)建立无向图的邻接矩阵，并实现插入、删除边的功能。2)建立有向图的邻接表，并实现插入、删除边的功能。1./*MGraph.cc:图的邻接矩阵存储表示和实现*//*包含图类型Graph定义；创建图；深度优先遍历；广度优先遍历*//*用到引用型参数，在TC下无法通过编译，VC等C++编译器可通过*/#include#include

2、tring.h>#include//含INT_MAX#defineVTypechar//顶点值类型#defineETypeint//边权值类型#defineMAXVNUM50//最大顶点个数#defineDIGRAPH0//有向图(网)#defineUNDIGRAPH1//无向图(网)#defineINVALIDINT_MAX//无效权值(最大整数表示无穷大)#defineEMPTY-1//"空"顶点序号//定义邻接矩阵表示的图类型Graph:typedefstruct{VT

3、ypev[MAXVNUM];//顶点序列(顶点编号从0开始)ETypew[MAXVNUM][MAXVNUM];//邻接矩阵intvn,en;//顶点数,边数intkind;//图的种类：=DIGRAPH表示有向图(网)，=UNDIGRAPH表示无向图(网)}Graph;intvisited[MAXVNUM];//访问标志数组(=1已访问，=0未访问)。遍历时用到的全局量。/*创建图G参数Vex是存放顶点序列的数组参数VVW是整数数组，以的形式依次存放各边的起止点序号(Vi,Vj)和权(Wij)，

4、-1是数据结束标志参数kind=DIGRAPH表示有向图(网)，=UNDIGRAPH表示无向图(网)*/voidCreateGraph(Graph&G,VType*Vex,intVVW[],intkind){inti,j,p,n,w;n=strlen(Vex);G.vn=n;//顶点数G.kind=kind;//图的种类//置顶点序列:for(i=0;i

5、=INVALID;//构造邻接矩阵:p=0;//VVW数组元素“指针”n=0;//边计数器while(VVW[p]!=-1){//只要p未到结束位置便继续:i=VVW[p];//边的起点序号j=VVW[p+1];//边的终点序号w=VVW[p+2];//边的权G.w[i][j]=w;//置邻接矩阵的(i,j)位置元素if(G.kind==UNDIGRAPH)//若是无向图(网),G.w[j][i]=G.w[i][j];//则置(i,j)的对称位置(j,i)n++;//边计数器加1p+=3;//p

6、指向下一组(Vi,Vj,Wij)}//endwhileG.en=n;//边数}//CreateGraph/*返回G中顶点i的一个未曾访问过的邻接点(序号)*/intNextAdjVex(Graph&G,inti){intj,a;a=EMPTY;//邻接点序号初始为"空"//在邻接矩阵的第v行找有效元素：for(j=0;j

7、访问过,则作为邻接点a:a=j;break;}//endif}//endforreturna;}//NextAdjVex/*访问顶点i*/voidvisit(Graph&G,inti){printf("%c",G.v[i]);}//visit/*从第i个顶点出发深度优先遍历连通图G*//*调用DFS前可能需初始化数组visited[]*/voidDFS(Graph&G,inti){inta;visit(G,i);//访问i顶点visited[i]=1;//标注i顶点已访问a=NextAdjVex

8、(G,i);//找出一个i的邻接点awhile(a!=EMPTY){//只要a存在便继续:if(visited[a]==0)//若a未曾访问,DFS(G,a);//则从a出发继续进行深度优先遍历。a=NextAdjVex(G,i);//找出i的下一个邻接点a}//endwhile}//DFS/*从第i个顶点出发深度优先遍历图G*/voidDFSTrav(Graph&G,inti){intk;//初始化各顶点的访问标志为0(未曾访问):for(k=0;k