North China Electric Power University I 5生成树 包含具有n个顶点的连通图G的全部n个顶点仅包 含其n-1条边的连通子图称为G的一个生成树。 华电计算机系
North China Electric Power University 5.生成树 华电计算机系 包含具有n 个顶点的连通图G 的全部n 个顶点,仅包 含其n-1条边的连通子图称为G 的一个生成树。 v1 v3 v4 v2 v1 v3 v4 v2 v1 v3 v4 v2 v1 v3 v4 v2 v1 v3 v4 v2
North China Electric Power University I ★图的存储结构 对于一个图需要存储的信息应该包括 (1)所有顶点的数据信息; (2)顶点之间关系(边或弧)的信息; (3)权的信息。 华电计算机系
North China Electric Power University 华电计算机系 对于一个图,需要存储的信息应该包括: (1).所有顶点的数据信息； (2).顶点之间关系(边或弧)的信息; (3).权的信息。 ★图的存储结构
North China Electric Power University I 邻接矩阵存储方法 数组存体方法 核心思想采用两个数组存储一个国 1.定义一个一维数组ⅴ ERTEX:m存放图中所有顶点 的数据信息 2.定义一个二维数组A1:n,1:m存放图中所有顶点之 间关系的信息(该数组被称为邻接矩阵)有 A1当项点v到顶点v有边时 0当顶点v到顶点v无边时 对于带权的图,有 A小≈w当顶点到顶点v有边且边的权为w 当页点到顶点无边时 华电计算机系
North China Electric Power University 一 .邻接矩阵存储方法 核心思想: 采用两个数组存储一个图. 1. 定义一个一维数组VERTEX[1:n]存放图中所有顶点 的数据信息. 2. 定义一个二维数组A[1:n,1:n]存放图中所有顶点之 间关系的信息(该数组被称为邻接矩阵),有 1 当顶点vi到顶点vj有边时 A[i, j]= 0 当顶点vi到顶点vj无边时 对于带权的图, 有 wij 当顶点vi到顶点vj有边,且边的权为wij A[i, j]= 当顶点vi到顶点vj无边时 oo 数组存储方法 华电计算机系
North China Electric Power University I Vertex[1: 4 A 1011 1110 Vertex2 1: 4 M 6∝7∝ 17 Cc CC CCCC C∝8∝ 华电计算机系
North China Electric Power University 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 A1 = v1 v2 v3 v4 Vertex1[1:4] v1 v2 v3 v4 Vertex2[1:4] 4 6 7 8 A2 = 华电计算机系 v1 v2 v3 v4 v1 v2 v3 v4 10 4 17 8
North China Electric Power University I 特点: (1)无向图的邻接矩阵一定是一个对称矩阵 (2)不带权的有向图的邻接矩阵一般是一个稀疏矩阵。 (3)无向图的邻接矩阵的第i行(第i列)非0或非∝ 元素的个数为第i个顶点的度数 (4)有向图的邻接矩阵的第i行非或非元素的个数为 第个顶点的出度第列非0或∝元素的个数为第 i个顶点的入度。 华电计算机系
North China Electric Power University (1).无向图的邻接矩阵一定是一个对称矩阵. (2).不带权的有向图的邻接矩阵一般是一个稀疏矩阵。 (3).无向图的邻接矩阵的第i 行(或第i 列)非0 或非 元素的个数为第i 个顶点的度数. (4).有向图的邻接矩阵的第i 行非0或非元素的个数为 第i 个顶点的出度;第i 列非0或非元素的个数为第 i 个顶点的入度。 特点: 华电计算机系