《图的存储结构》PPT课件

《《图的存储结构》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示四、无向图的邻接多重表存储表示7.2图的存储结构￡7.2图的存储结构￡7.2.1数组表示法（邻接矩阵）（1）定义数组表示法：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。（2）C语言描述#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,

2、DN,UDG,UDN}GraphKind;//{有向图，有向网，无向图，无向网}typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型。对无权图，用1//或0表示相邻否；对带权图，则为权值类型。InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum

3、;//图的当前顶点数和弧数GraphKindkind;//图的种类标志}MGraph;Aij={0(i,j)VR1(i,j)VRBACDFE定义:矩阵的元素为有向图的邻接矩阵为非对称矩阵ABECD在有向图中,统计第i行1的个数可得顶点i的出度，统计第j行1的个数可得顶点j的入度。在无向图中,统计第i行(列)1的个数可得顶点i的度。（3）邻接矩阵中顶点度的求法对于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的元素之和，即：对于有向图，顶点vi的出度OD(vi)为第i行的元素之和，顶点vi的入度ID(vi)为第j列的元素之和。（4）网的邻接矩阵网

4、的邻接矩阵可定义为：wi,j若或(vi,vj)∈VRA[i][j]=∞反之例如，下图列出了一个有向网和它的邻接矩阵。(b)邻接矩阵(a)网N4538791655V1V2V6V3V5V4（5）图的构造算法7.1如下：StatusCreateGraph(MGraph&G){//采用数组（邻接矩阵）表示法，构造图G。scanf(&G.kind);switch(G.kind){caseDG:returnCreateDG;//构造有向图GcaseDN:returnCreateDN;//构造有向网GcaseUDG:returnCreateUDG;//

5、构造无向图GcaseUDG:returnCreateUDG;//构造无向网Gdefault:returnERROR;}}//CreateGraph算法7.1是在邻接矩阵存储结构MGraph上对图的构造操作的实现框架，它根据图G的种类调用具体构造算法。StatusCreateUDN(MGraph&G){//采用数组（邻接矩阵）表示法，构造无向网G。scanf(&G.vexnum,&G.arcnum,&IncInfo);//IncInfo为0则各弧不含其他信息for(i=0;i

6、for(i=0;i的权值if(IncInfo)Input(*G.arcs[i][j].info)

7、;//若弧含有相关信息，则输入G.arcs[j][i]=G.arcs[i][j];//置的对称弧}//forreturnOK;}//CreateUDN算法7.2如下：算法7.2构造一个具有n个顶点和e条边的无向网G。其时间复杂度为O(n2+e*n)，其中对邻接矩阵G.arcs的初始化耗费了O(n2)的时间。7.2.2邻接表表示法(AdjacencyList)用邻接矩阵存储弧或边的信息，比较浪费空间，如果我们只存储图中已有的弧或边的信息，就可以节省空间。而图中所有顶点都是依附于某两个顶点的，因此如果对图中的所有顶点都建立一个单

8、链表来存储所有依附于该顶点的弧或边，就可以把图中所有已有的弧或边的信息保存下来。而对于图中所有