欢迎来到天天文库
浏览记录
ID:58231095
大小:302.50 KB
页数:29页
时间:2020-09-05
《图存储结构课件.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
此文档下载收益归作者所有