第七章图 7.2图的存储结构 数组表示法 邻接表
7.2 图的存储结构 一 数组表示法 二 邻接表 第七 章 图
§7.2图的存储结构 V3) V3 图的存储结构至少要保存两类信息: 1)顶点的数据 如何表示顶点间的关系? 2)顶点间的关系 顶点的编号 约定: G=<V,E>是图,V={vo,1,V2,…,vn-1},设顶点的 角标为它的编号
§ 7.2 图的存储结构 图的存储结构至少要保存两类信息： 1)顶点的数据 2)顶点间的关系 约定: G=<V, E>是图, V={v0,v1,v2, … vn-1 },设顶点的 角标为它的编号 如何表示顶点间的关系？ 顶点的编号 V0 V3 V4 V1 V2 V0 V1 V2 V3
§72图的存储结构 在数组表示法中, 数组表示法(邻接矩阵用邻接矩阵表示顶点间的关系 邻接矩阵:G的邻接矩阵是满足如下条件的n阶矩阵: ALi]Lj] 若(vi,vi+1)∈E或〈vi,vi+1∈E(V 0否则 ⑩ 01010 9 10101 0101 0000 10100 0001 01100 1000
邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵： A[i][j]= 1 若(vi,vi+1)E 或 <vi,vi+1>E 0 否则 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 一 数组表示法(邻接矩阵表示) 在数组表示法中， 用邻接矩阵表示顶点间的关系 § 7.2 图的存储结构 V0 V3 V4 V1 V2 V0 V1 V2 V3
§72图的存储结构 无向图数组表示法特点: 1)无向图邻接矩阵是对称矩阵,同一条边表示了两次; 2)顶点v的度:等于二维数组对应行(或列)中1的个数; 3)判断两顶点v、u是否为邻接点:只需判二维数组对应分量是否 为1; 4)顶点不变,在图中增加、删除边:只需对二维数组对应分量赋 值1或清0 5)设图的顶点数为n,存储图用一维数组,数组元素有m个 (m>=n),则G占用存储空间:m+n2;G占用存储空间只与它的顶点 数有关,与边数无关;适用于边稠密的图; 对有向图的数组表示法可做类似的讨论 01010 数组表示法的空间代价 只与图的顶点数有关 01100
无向图数组表示法特点： 1）无向图邻接矩阵是对称矩阵，同一条边表示了两次； 2）顶点v的度：等于二维数组对应行（或列）中1的个数； 3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否 为1； 4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋 值1或清0； 5）设图的顶点数为 n ,存储图用一维数组, 数组元素有 m 个 （m>=n),则 G占用存储空间：m+n2；G占用存储空间只与它的顶点 数有关，与边数无关；适用于边稠密的图； 对有向图的数组表示法可做类似的讨论 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 数组表示法的空间代价 只与图的顶点数有关 § 7.2 图的存储结构 V0 V3 V4 V1 V2
§7.2图的存储结构 图的基本操作: )求无向图某顶点ⅴi的度(或有向图中ⅴi的出度)。A[i[0]到 A[i][n-1]中的非0个数,即数组A中第i行的非0元素的个数; 2)求有向图某顶点ⅵ的入度。:A[0][订到A[n-1][i]中的非0 个数,即数组A中第i列的非0元素的个数; 3)检测图中的总边数。扫描整个数组A,统计出数组中非0元素的 个数。无向图的总边数为非0元素个数的一半,而有向图的总弧数 为非0元素个数; @(0 010 10101 0110 0000 011 0001 10100 V2(V3 1000 0 100
图的基本操作： 1）求无向图某顶点vi的度(或有向图中vi的出度)。A[i][0]到 A[i][n-1]中的非0个数，即数组A中第i 行的非0 元素的个数； 2）求有向图某顶点vi 的 入度。： A[0][i]到A [n-1][i] 中的非0 个数，即数组A中第i 列的非0 元素的个数； 3）检测图中的总边数。扫描整个数组A，统计出数组中非0元素的 个数。无向图的总边数为非0元素个数的一半，而有向图的总弧数 为非0元素个数； 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 § 7.2 图的存储结构 V0 V3 V4 V1 V2 V0 V1 V2 V3 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0