数据结构复习笔记图的数组(邻接矩阵)存储表示及重要的基本操作

《数据结构复习笔记图的数组(邻接矩阵)存储表示及重要的基本操作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图的数组(邻接矩阵)存储表示及重要的基本操作/*图的数组(邻接矩阵)存储表示及重要的基本操作*/#defineINFINITYINT_MAX/*用整型最大值代替∞*/#defineMAX_VERTEX_NUM20/*最大顶点个数*///结构真的很重要，我觉得typedefenum{DG,DN,UDG,UDN}GraphKind;/*{有向图,有向网,无向图,无向网}*/typedefstruct{VRTypeadj;/*顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值*/InfoType*info;/*该弧相关信息的指针(可无)*/}ArcCell,

2、AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*二维数组*/typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/AdjMatrixarcs;/*邻接矩阵*/intvexnum,arcnum;/*图的当前顶点数和弧数*/GraphKindkind;/*图的种类标志*/}MGraph;邻接矩阵的表示://以下的重要基本操作，考试时应该不会让单独写吧，最多填空。了解一下，很常用的操作。1StatusLocateVex(MGraphG,VertexTypeu){/*初始条件：图G存在，u和G

3、中顶点有相同特征*//*操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回NULL*/inti;for(i=0;i

4、量for(i=0;i

5、相关信息,则输入}G.kind=DG;//图的类型returnOK;}//CreateUDNStatusCreateUDN(MGraph&G){//采用数组（邻接矩阵）表示法，构造无向网Gscanf(&G.vexnum,&G.arcnum,&IncInfo);//IncInfo为0则各弧不含其它信息for(i=0;i

6、nfo}for(k=0;k的权值2if(IncInfo)Input(*G.arcs[i][j].info);//若弧含有相关信息,则输入G.arcs[j][i]=G.arcs[i][j];//置的对称弧}G.kind=UDN;//图的类型returnOK;}//CreateUDNSta

7、tusFirstAdjVex(MGraphG,VertexTypev){/*初始条件：图G存在，v是G中某个顶点*//*操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1*/intj=0;//用来在非网图中判断邻接顶点k=LocateVex(G,v);/*k为顶点v在图G中的序号*/if(G.kind%2)/*网*/j=INFINITY;for(i=0;i