非线性数据结构--图.ppt

LZQ@CEEC 非线性数据结构--图 概念 有向图、无向图、网 存储 邻接矩阵、邻接表 遍历 深度优先、广度优先 2.5 图的逻辑结构 图是对结点的前趋和后继个数不加限制的数据结构,用来描述元素之间“多对多”的关系。 一. 图的定义 1. 定义: 图 G =(V，E) 其中：V:顶点的非空集合 E:顶点的偶对---边的集合 例 V={v1,v2,v3,v4} E={（v1,v2),(v1,v3), （v2,v1),(v2,v3), （v2,v4),(v3,v1), （v3,v2),(v4,v2) } 2. 有向图、无向图 无向图: 图中顶点的偶对是无序的，称此图为无向图，其偶对用(vx，vy)表示。 有向图: 图中顶点的偶对是有序的，称此图为有向图,偶对用vx,vy表示。 G2=（V，E） V={ 1,2,3,4} E={〈1,2,1,3 ,3,4,4,1} 3. 边和弧 边: 无向图中顶点的偶对，写成（Vx，Vy）或（Vy，Vx）。 弧: 有向图中顶点的偶对,〈Vx,Vy〉表示从Vx到Vy。 弧头: 弧的终点 弧尾: 弧的起点 弧 〈Vx，Vy〉 弧尾Vx 弧头Vy 4. 邻接点 顶点: 图中的结点 邻接点: 无向图中，若边(Ｖx,Ｖy)?E， 则Ｖx、Ｖy互为邻接点。 有向图中，若弧(Ｖx,Ｖy)?E， 则Ｖy是Ｖx的邻接点。 5. 顶点的度 无向图:顶点的度是连接该顶点的边的条数。 例如，G1中V2的度为3，V4的度为1。 有向图 1)入度:以某顶点为弧头的弧的数目。 G2中顶点1的入度为1。 2)出度:以某顶点为弧尾的弧的数目。 顶点1的出度为2。 3)顶点的度=入度+出度。顶点1的度=2+1=3。 6.路径、长度 路径 图中从顶点Vx到顶点Vy的顶点序列称为从Vx到Vy的路径,路径可能是不唯一的。 例如:G1中V1到V3的路径为:(V1V2V3)或(V1V3) G2中，1到4的路径为134。 长度 路径上边或弧的数目。 例如，G1中V1到V3的长度为1或2； G2中1到4的长度为2。 7.网、权 权 若图的边或弧带有与之相关的数，称此数为该边或弧的权。 权通常用来表示从一个顶点到另一个顶点的距离或费用。 网 带权的图称为网。 2.6 图类的存储结构 常用的存储结构： 邻接矩阵表示法 邻接表表示法 一.邻接矩阵 图为V和E的集合,因此: 用一个一维数组存放所有顶点； 用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。 邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。 1.无向图邻接矩阵 定义 设图G=(V,E)是有n(n?1)个顶点的图，则G的邻接矩阵是具有下述性质的对称阵： 1 (Vi，Vj）? E A[i][j]=A[j][i] = 0 (Vi，Vj）? E G1的邻接矩阵为： 2.有向图邻接矩阵 定义 设图G=（V，E）是有n（n ? 1）个顶点的图，则G的邻接矩阵是具有下述性质的nxn的方阵： 1 〈Vi，Vj? E A[i][j] = 0 〈Vi，Vj? E 例如，G2的邻接矩阵为： 3.借助邻接矩阵求顶点的度 无向图 第i行（或第i列）的元素之和是顶点Vi的度。例，G1中V2的度是3。 有向图 第i行的元素之和为顶点Vi的出度；第j列的元素之和为顶点Vj的入度。例，G2中，V2的出度为0，V1的入度为1。 4.网的邻接矩阵 定义： Wij （Vi,Vj）或〈Vi,Vj〉? E A[i][j] = ? （Vi,Vj）或〈Vi,Vj〉? E 二. 邻接表 图的链式存储结构 1) 为每个顶点建立一个单链表， 2) 第i个单链表中包含顶点Vi的所有邻接顶点。 二. 邻接表 结点组成： 每个链表附设一个头结点，结构为： 1. 无向图的邻接表 2.有向图G2的邻接表 2.7 图的遍历 图的遍历 从指定顶点出发访问图中每一个顶点，使每个顶点都被访问且只被访问一次 常用