图存储结构课件.ppt

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

1、7.2图的存储结构及实现是否可以采用顺序存储结构存储图?图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。邻接矩阵（数组表示法）基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。7.2图的存储结构及实现假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：arc[i][j]＝1若(vi,vj)∈E（或

2、∈E）0其它无向图的邻接矩阵的特点？无向图的邻接矩阵7.2图的存储结构及实现V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4主对角线为0且一定是对称矩阵。如何求顶点i的度？无向图的邻接矩阵7.2图的存储结构及实现V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4邻接矩阵的第i行（或第i列）非零元素的个数。如何判断顶点i和j之间是否存在边？无向图的邻接矩阵7.2图的存储结构及实现V1V3V4V2

3、V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4测试邻接矩阵中相应位置的元素arc[i][j]是否为1。如何求顶点i的所有邻接点？无向图的邻接矩阵7.2图的存储结构及实现V1V3V4V2V1V2V3V4vertex=0101101101001100arc=V1V2V3V4V1V2V3V4将数组中第i行元素扫描一遍，若arc[i][j]为1，则顶点j为顶点i的邻接点。7.2图的存储结构及实现有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=

4、V1V2V3V4V1V2V3V4有向图的邻接矩阵一定不对称吗？不一定，例如有向完全图。7.2图的存储结构及实现有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求顶点i的出度？邻接矩阵的第i行元素之和。7.2图的存储结构及实现有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何求顶点i的入度？邻接矩阵的第i列元素之和。7.2图的存储结构及实现有向图的邻接矩阵V1V2V3V

5、4V1V2V3V4vertex=0110000000011000arc=V1V2V3V4V1V2V3V4如何判断从顶点i到顶点j是否存在边？测试邻接矩阵中相应位置的元素arc[i][j]是否为1。网图的邻接矩阵7.2图的存储结构及实现网图的邻接矩阵可定义为：arc[i][j]＝wij若(vi,vj)∈E（或∈E）0若i=j∞其他V1V2V3V42785025∞∞0∞∞∞∞087∞∞0arc=图的邻接矩阵存储表示法typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstructArcNode/*弧

6、*/{intadj;}ArcNode;typedefstruct{VertexDatavexs[MAX_VERTEX_NUM];/*顶点向量*/ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接矩阵*/intvexnum,arcnum;/*图的顶点数和弧数*/GraphKindkind;/*图的种类标志*/}AdjMatrix;7.2图的存储结构及实现邻接矩阵中图的基本操作——创建图确定图的顶点个数和边的个数；2.输入顶点信息存储在一维数组vertex中；3.初始化邻接矩阵；4.依次输入每条边存储

7、在邻接矩阵arc中；4.1输入边依附的两个顶点的序号i,j；4.2将邻接矩阵的第i行第j列的元素值置为1；4.3将邻接矩阵的第j行第i列的元素值置为1；7.2图的存储结构及实现intCreateDN(AdjMatrix*G)/*创建一个有向网*/{inti,j,k,weight;VertexDatav1,v2;scanf("%d,%d",&G->arcnum,&G->vexnum);/*输入图的顶点数和弧数*/for(i=0;ivexnum;i++)/*初始化邻接矩阵*/for(j=0;jvexnum;j++)G->arcs[

8、i][j].adj=INFINITY;for(i=0;ivexnum;i++){scanf("%c",&G->vexs[i]);/*输入图的顶点*/}for