数据结构图结构_(动态PPT)

《数据结构图结构_(动态PPT)》由会员分享，可在线阅读，更多相关《数据结构图结构_(动态PPT)（141页珍藏版）》请在金锄头文库上搜索。

1、1,本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习，读者应该： 1) 了解图的定义和术语 2) 掌握图的各种存储结构 3) 掌握图的深度优先搜索和广度优先搜索遍历算法 4) 理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法,本章学习导读,2,图（Graph）是一种较线性表和树更为复杂的非线性结构。 在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。 在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。

2、 然而在图形结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。 图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。,3,7.1 图的定义 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径,第七章 图,4,图定义 图G由两个集合V和E组成，记为 G = ( V , E ) 其中， V是顶点的有穷非空集合， E是V中顶点偶对的有穷集， 这些顶点偶对称为边。通常V(G)和E(G)分别称为图的顶点集

3、合和边集合。 注： E(G)可以为空集。,7.1 图的定义和术语,5,7.1 图的定义和术语,图的数据结构的形式化定义 （p156）,G = ( V , E ) 其中 V = x | x dataobject E =VR VR=| p(x,y) ( x , y V ) VR是两顶点间的关系的集合，即边的集合。,6,图的术语,有向图: 对一个图G，若边集E(G)为有向边的集合，则称该图为有向图。,G1=（V，E） V=v1, v2, v3, v4 E=, , , 其中表示从x到y的一条弧（arc），A为弧集合，x为弧尾（tail），y为弧头（head),x弧尾,y弧头,7,图的术语,无向图: 对

4、一个图G，若边集E(G)为无向边的集合，则称该图为无向图。,G2=（V，E） V=v1, v2, v3, v4, v5 E=(v1, v2), (v1, v3), (v2, v3), (v3, v4), (v2,v5), (v3,v5) 其中，(x, y)表示x与y之间的一条连线，称为边（edge）,8,图的术语,设n为顶点数，e为边或弧的条数 对无向图有：0 e n(n-1)/2 有向图有：0 e n(n-1),证明：对有向图，每个顶点至多有n-1条边与其它的n-1个顶点相连，则n个顶点至多有n(n-1)条边。但对无向图，每条边连接2个顶点，故最多为n(n-1)/2,9,图的术语,端点和邻接

5、点 在一个无向图中，若存在一条边, 则称vi，vj为该边的两个端点，并称它们互为邻结点。,10,图的术语,起点和终点 在一个有向图中，若存在一条边, 则称该边是顶点vi的一条出边，是vj的一条入边，称vi是起始端点（或起点），称vj是终止端点（或终点）,并称它们互为邻结点.,11,图的术语,度 图中每个顶点的度是以该顶点为一端点的边的数目。记为 D(V) 。 入度和出度 对于有向图，入度为以该顶点为终点的边的数目，出度为以该顶点为起点的边的数目。,例 D(v1)=3,无向图的度数为依附于顶点v 的边数；有向图的度数等于以 顶点v 为弧头的弧数与以顶点v 为弧尾的弧数之和,例 D(v1)=2,1

6、2,图的术语,子图 设有两个图G=（V，E） G=（V，E）中，若V是V的子集， E是E的子集，则称G是G子图。,13,图的术语,简单图 对不含多重边和自环的图。,简单图,非简单图,14,图的术语,完全图 边达到最大的图,无向完全图：具有n(n-1)/2条边的简单图称为无向完全图 有向完全图：具有n(n-1)条边的有向图。 稀疏图： 边或弧很少的图。 稠密图： 边或弧很多的图。 权：与图的边或弧相关的数。 网：边或弧上带有权值的图。,15,图的术语,路径 非空有限点、弧交替序列， W=v0, a1,v1, , ak,vk 使得i=1,2,k , 弧ai的头vi , 尾为vi-1 。,路径长度：

7、路径上边或弧的数目,16,图的术语,简单路径：除首尾两点外，其他各点都不相同的路径称为简单路径。,简单路径,17,图的术语,回路:无重复边的闭路径。,环：闭的简单路径，称为环。,回路但不是环,环,18,图的术语,连通图 ：任何两点都有路径的图。 无向图：若图中任意两个顶点vi,vj都是连通 的，则称该图是连通图(vivj) 有向图：若图中任意两个顶点vi,vj，都存在 从vi到vj 和从 vj到vi的路径，则称 该有向图为强连通图 (vivj),19,图的术语,连通分量： 无向图：无向图中极大连通子图，称为 连通分量 有向图：有向图中极大强连通子图，称为 强连通分量,20,生成树,图的术语,生

8、成树 一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。,有向树 如果一个有向图恰有一个顶点入度为0，其余顶点的入度均为1，则是一棵有向树。,21,生成树、生成森林 生成树 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。 生成树是对连通图而言的 是连通图的极小连通子图 包含图中的所有顶点 有且仅有n-1条边 非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。,一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。,22,图有两种存储结构 邻

9、接矩阵 邻接表,7.2 图的存储结构,23,7.2.1 邻接矩阵 邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设G(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵。,7.2 图的存储结构,无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。 在有向图中： 第 i 行 1 的个数就是顶点 i 的出度， 第 j 列 1 的个数就是顶点 j 的入度。 在无向图中, 第 i 行 (列) 1 的个数就是顶点i 的度。,24,一、邻接矩阵（用二维数组表示）,例如：G1的邻接矩阵,例如：G2的邻接矩阵,无向图的邻接矩阵为对称矩阵,25,对于无

10、向图，（vi，vj）和（vj，vi）表示同一条边，因此，在邻接矩阵中Aij=Aji。 无向图的邻接矩阵是（关于主对角线）对称矩阵，可用主对角线以上（或以下）的部分表示。 对有向图，弧和表示方向不同的两条弧，Aij和Aji表示不同的弧，所以有向图的邻接矩阵一般不具有对称性。 邻接矩阵表示法适合于以顶点为主的运算。,26,对于有向图，顶点vi的出度OD (vi)等于邻接矩阵第i行元素之和；顶点vi的入度ID (vi)等于邻接矩阵第i列元素之和，即 ：,对于无向图，顶点vi的度等于邻接矩阵第i行的元素之和，即：,OD (vi)=,ID (vi)=,TD（vi）=,27,若G是网（有权图），邻接矩阵定

11、义为,如图：,Wij 若 或 E(G) A i，j = 0或 若其它,28,顶点表: 一个记录各个顶点信息的一维数组， 邻接矩阵：一个表示各个顶点之间的关系（边或弧）的二维数组。 使用邻接矩阵存储结构，可用一维数组表示图的顶点集合，用二维数组表示图的顶点之间关系（边或弧）的集合，数据类型定义如下： #define MAX_VERTEX_NUM 20 /最大顶点数 typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; /邻接矩阵类型 typedef struct VertexType vexsMAX_VERTEX_NUM; /顶点表 AdjMatr

12、ix arcs; /邻接矩阵 int vexnum， arcnum; /图的顶点数和弧数 MGraph; 由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀疏矩阵，因此会造成一定存储空间的浪费。,29,7.2.2 邻接表 图的链式存储结构 1) 为每个顶点建立一个单链表， 2) 第i个单链表中包含顶点Vi的所有邻接顶点。 邻接表是图的一种链式存储结构。类似于树的孩子链表表示法。在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为边（或弧）结点。,30,1. 无向图邻接表,31,2.有向图邻接表,如图G1的邻接表为：,32

13、,在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。 设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个顶点结点，2e 个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。 建立邻接表的时间复杂度为O(n*e)。若顶点信息即为顶点的下标，则时间复杂度为O(n+e)。,33,存储表示 typedef struct ArcNode int adjvex; /该弧所指向的顶点的位置 struct ArcNode *nextarc; /指向下一条弧的指针 int * info; /该弧相关信息的指针 ArcNode; /边结点类型

14、typedef struct VNode VertexType data; /顶点信息 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VERTEX_NUM; /邻接表 typedef struct AdjList vertices; int vexnum,arcnum; /图的当前顶点数和弧数 int kind; /图的种类标志 ALGraph;,34,1. 无向图邻接表,二、邻接表,35,1. 无向图邻接表,对图中每个顶点Vi建立一个单链表，链表中的结点表示依附于顶点Vi的边，每个链表结点为两个域.,其中：邻接点域（adjvex）记

15、载与顶点Vi邻接的顶点信息； 链域（nextarc）指向下一个与顶点Vi邻接的链表p结点,每个链表设一个头结点，头结点结构为：,其中：vexdata存放顶点信息（姓名、编号等）； firstarc指向链表的第一个结点。,二、邻接表,36,二、邻接表（adjacency list）,如图G2的邻接表为：,37,B,A,C,D,F,E,例 2,38,2.有向图邻接表,特点：1. n个顶点，e条弧的有向图，需n个表头结点，e 个表结点 2. 第 i 条链表上的结点数，为 Vi 的出度 （求顶点的出度易，求入度难）,如图G1的邻接表为：,39,1 4,2,3,0 1,2,0 1 2 3 4,A B C D E,2.有向图的邻接表,A,B,E,C,F,可见，在有向图的邻接表中不易找到指向该顶点的弧。,40,3. 有向图逆邻接表,此时，第i条链表上的结点数，为Vi的入度,如图G1的逆邻接表为：,G1,41,A,B,E,C,D,有向图的逆邻接表,A B C D E,3,0,3,4,2,0,0 1 2 3 4,在有向图的邻接表中，对每个顶点，链接的是指向该顶点的