二、图的存储结构 前面在讨论树和线性表的存储结构时,用 到两种存储结构:顺序表和链表。但图结构 中的结点间没有确定的关系(没根),任意 两点之间都可能存在联系,因此无法用顺序 结构来存放图的顶点数据。但借助数组可以 用来表示顶点之间的关系。 实际上,在图的存储结构中,常用下面两 种方法: 3接矩阵表元法 □上一页 3接表表元法 停止放映 第16页
下一页 上一页 停止放映 第 16 页 二、图的存储结构 前面在讨论树和线性表的存储结构时，用 到两种存储结构：顺序表和链表。但图结构 中的结点间没有确定的关系（没根），任意 两点之间都可能存在联系，因此无法用顺序 结构来存放图的顶点数据。但借助数组可以 用来表示顶点之间的关系。 实际上，在图的存储结构中，常用下面两 种方法： –邻接矩阵表示法 –邻接表表示法
1、邻接矩阵表示法 ●根据图的定义可知,图的逻辑结构分为两部 分:V和E的集合。因此, 用一个一维数组存放图中所有顶点数据; 用一个二维数组存放顶点间关系(边或 弧)的数据,称这个二维数组为郛接矩 阵 邻接矩阵又分为有向图接矩和无向 图邻接矩阵 □上一页 停止放映 第17页
下一页 上一页 停止放映 第 17 页 1、邻接矩阵表示法 ⚫ 根据图的定义可知，图的逻辑结构分为两部 分：V和E的集合。因此， –用一个一维数组存放图中所有顶点数据； –用一个二维数组存放顶点间关系（边或 弧）的数据，称这个二维数组为邻接矩 阵。 –邻接矩阵又分为有向图邻接矩阵和无向 图邻接矩阵
有向图邻接矩阵 定义 设图G=(V,E)是有n(n≥1)个顶点的图,则G的 邻接矩阵是具有下述性质的nxn的方阵,元素为: 1当〈Vi,Vj>∈E时 AL i, j] 当〈Vi,Vj>∈E时 例如,G2的邻接矩阵为: 0110 2 G nodes= 0000 3 A GArc= 0001 □上一页 4 10004x4 停止放映 G2 第18页
下一页 上一页 停止放映 第 18 页 有向图邻接矩阵 ⚫ 定义 设图G=（V，E）是有n（n 1）个顶点的图，则G的 邻接矩阵是具有下述性质的nxn的方阵，元素为： 1 当〈Vi，Vj> E 时 A[ i，j] = 0 当〈Vi，Vj> E 时 例如，G2的邻接矩阵为： G.nodes= 1 2 3 4 A= G.Arc= 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 4x4 1 3 2 4 G2
无向图邻接矩阵 ●定义 v2 设图G=(V,E)是有n(n≥1)个顶点的图,则G的邻 接矩阵是具有下述性质的对称阵,元素为 1当(Vi,Vj)∈E时 AL i, j] =Alj, i] 0 0当(vi,Vj)gE时 3v4例如,Gl的邻接矩阵为: G1 □上一页 G nodes 3A=Gedge=/101 1 2 1100 停止放映 4 01004x4 第19页
下一页 上一页 停止放映 第 19 页 无向图邻接矩阵 ⚫ 定义 设图G=（V，E）是有n（n 1）个顶点的图，则G的邻 接矩阵是具有下述性质的对称阵，元素为： 1 当(Vi，Vj） E 时 A[ i，j] =A[j,i] = 0 当(Vi，Vj） E 时 例如，G1的邻接矩阵为： G.nodes = 1 2 3 4 A=G.edge = 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 4x4 o o o o v1 v2 v3 v4 G1
求图中顶点的度 ●借助邻接矩阵,可以很容易地求出图中顶点 的度。 2 无向图邻接矩阵的第i行(或第i列) 的元素之和是顶点Vi的度。例,G1中V2 的度是3。 有向图邻接矩阵第i行的元素之和为顶 点Ⅵ的出度;第j列的元素之和为顶点Vj v3 GI 的入度。例,G2中,V2的出度为0(第2 行的元素之和为0),Ⅵ1的入度为1(第1 □上一页 列的元素之和为1)。 0110 停止放映 A= GArc= 0000 0001 G2 1000 第20页
下一页 上一页 停止放映 第 20 页 求图中顶点的度 ⚫ 借助邻接矩阵,可以很容易地求出图中顶点 的度。 –无向图 邻接矩阵的第i行（或第i列） 的元素之和是顶点Vi的度。例，G1中V2 的度是3。 –有向图 邻接矩阵第i行的元素之和为顶 点Vi的出度；第j列的元素之和为顶点Vj 的入度。例，G2中，V2的出度为0（第2 行的元素之和为0），V1的入度为1（第1 列的元素之和为1）。 o o o o v1 v2 v3 v4 G1 A= G.Arc= 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 3 2 4 G2