电子斜技大学 软件技术基础 3.6.2图的物理存储 主讲教师：刘民岷 航空航天学院 a■ 软件技术基础课程组
软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组
2、图的物理存储 前面在讨论树和线性表的存储结构时，用到两种存储结 构：顺序表和链表。 实际上，在图的存储涉及到顶点的存储和边的存储。顶 点可以使用数组进行存储，边则常用下面两种方法存储： ·邻接矩阵 邻接表 电子科技大学刘民岷 图 2
电子科技大学 刘民岷 图 2 前面在讨论树和线性表的存储结构时，用到两种存储结 构：顺序表和链表。 实际上，在图的存储涉及到顶点的存储和边的存储。顶 点可以使用数组进行存储，边则常用下面两种方法存储： • 邻接矩阵 • 邻接表
2、图的物理存储（续） 2.1邻接矩阵表示法 。 根据图的定义可知，图的逻辑结构分为两部分：V和E的 集合，因此可以： 用一个一维数组存放图中所有顶点数据； 用一个二维数组存放顶点间关系（边或弧)的数据，称这个二维 数组为邻接矩陲。 邻接矩阵又分为有向图邻接矩陲和无向图邻接矩哇。 3 4 6 a.无向图G b.有向图G2 电子科技大学刘民岷 图 3
电子科技大学 刘民岷 图 3 2.1 邻接矩阵表示法 • 根据图的定义可知，图的逻辑结构分为两部分：V和E的 集合，因此可以： – 用一个一维数组存放图中所有顶点数据； – 用一个二维数组存放顶点间关系（边或弧）的数据，称这个二维 数组为邻接矩阵。 – 邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。 1 2 3 4 5 a.无向图G 1 6 2 3 4 5 b.有向图G2
2、图的物理存储（续） 2.1邻接矩阵表示法 ·有向图邻接矩阵： -定义 设图G=(V,E)是有n(n≥I)个顶点的图，则G的邻接矩阵是具有下述性质 的nXn的方阵，元素为： 当<Vi,Vj>∈E时 A[i.jl= 0 当<Vi,Vj>E时 -例如，G2的邻接矩阵为： 3 G2 2 G.nodes G.Arc 3 4 电子科技大学刘民岷 图 4
电子科技大学 刘民岷 图 4 2.1 邻接矩阵表示法 • 有向图邻接矩阵： – 定义 设图G=（V，E）是有n（n 1）个顶点的图，则G的邻接矩阵是具有下述性质 的n×n的方阵，元素为： 1 当<Vi，Vj> E 时 A[i,j]= 0 当<Vi，Vj> E 时 – 例如，G2的邻接矩阵为： 1 2 3 4 G2 = 4 3 2 1 G.nodes = 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 G.Arc
2、图的物理存储（续） 2.1邻接矩阵表示法 ·无向图邻接矩阵： 定义 设图G=(V,E)是有n(n≥l)个顶点的无向图图，则G的邻接矩阵是 具有下述性质的n×n的方阵，元素为： 1当(Vi,Vj)eE时 A[ij]- 0 当(Vi,Vj)eE时 3 例如，G,的邻接矩阵为： 1 0 1 2 1 0 1 1 G.nodes= 3 G.Edge= 11 0 4 1 电子科技大学刘民岷 图 5
电子科技大学 刘民岷 图 5 2.1 邻接矩阵表示法 • 无向图邻接矩阵： – 定义 设图G=（V，E）是有n（n 1）个顶点的无向图图，则G的邻接矩阵是 具有下述性质的n×n的方阵，元素为： 1 当(Vi，Vj) E 时 A[i,j]= 0 当(Vi，Vj) E 时 – 例如，G1的邻接矩阵为： 1 2 3 4 G1 = 4 3 2 1 G.nodes = 0 1 0 0 1 1 0 0 1 0 1 1 0 1 1 0 G.Edge