《《数据结构(C／C++描述)》-阮宏一-电子教案 第7章 图》由会员分享，可在线阅读，更多相关《《数据结构(C／C++描述)》-阮宏一-电子教案 第7章 图（115页珍藏版）》请在金锄头文库上搜索。
1、第 7 章 图,本章介绍另一种非线性数据结构 图 图：是一种多对多的结构关系，每个元素 可以有零个或多个直接前趋；零个或多个直接 后继。,7.2 图的存储结构,7.3 图的遍历及图的连通分量,7.4 生成树和最小生成树,7.1 图的基本概念,7.5 最短路径,7.6 拓扑排序与关键路径,图是由一个顶点集 V 和一个边集 E 构成的数据结构。可表示为： Graph = （V, E） 其中 V 是顶点的非空有限集合，E 是边的有限集合，边是顶点的无序对或有序对。,7.1 图的基本概念,无序对对应的边称为无向边或边，有序对对应的边称为有向边或弧。,例：G1=（V1, E1） V1= v1,v2,v3
2、,v4 ,v5 E1=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),G1图示,无序对 (vi, vj) 表示连接顶点 vi、vj的边， 称为无向边。,由顶点集和边集构成的图，称作无向图。,例： G2 =（V2, E2） V2 = v1,v2,v3,v4 E2= , , , ,G2图示,称由顶点集和弧集构成的图为有向图。,有序对 表示以vi为起点、以 vj为终点的有向线段， 称为有向边或弧。,B,设图 G=(V, E) 和图 G=(V,E), 若 VV, EE, 则称 G 为 G 的子图。,弧或边带权的图分别称作有向网或无向网。,名词和术语,A,
3、B,C,D,无向图 G2,A,B,C,D,A,C,A,B,C,D,有向图G1的子图,A,B,C,D,E,A,B,D,E,A,A,B,C,D,A,B,C,D,E,无向图G2的子图,有向图 G1,假设图中有 n 个顶点，e 条边，则,含有 e=n(n-1)/2 条边的无向图称作完全图;,含有 e=n(n-1) 条弧的有向图称作有向完全图;,若边或弧的个数 e nlogn，则称作稀疏图，否则称作稠密图。,例：判断下列 4 种图形各属什么类型？,无向,无向图(树),有向图,有向,n(n-1)/2 条边,n(n-1) 条边,完全图,完全图,若顶点v 和顶点w 之间存在一条边， 则称顶点 v 和 w 互为
4、邻接点，,例如:,Degree(B) = 3,Degree(A) = 2,称边(v, w) 和顶点 v 和 w 相关联。 和顶点v 关联的边的数目称为顶点的度。,右图中,顶点的出度: 由顶点v 射出的弧的数目;,顶点的入度: 以顶点v为终点的弧的数目。,例如:,I D(B) = 2,OD(B) = 1,TD(B) = 3,对有向图来说，由于弧有方向性，则顶点的度有入度和出度之分。,顶点的度：(TD)= 出度(OD)+入度(ID),设 图 G 的顶点数为 n，边数为 e， 则 图的所有顶点的度数之和 = 2*e。,图中顶点的度数与边数的关系：,因为： 每条边对图的顶点的度数“贡献” 2 度。,设
5、由图G中的顶点u，经图G中的边或弧能够到达G中的顶点w，则称从顶点 u 到顶点 w 之间存在一条路径。,如:从 A 到 F 长度为 3 的路径： A,B,C,F ,简单路径:指序列中顶点不重复出现的路径。,简单回路:指序列中只有第一个顶点和最后一个顶点相同的路径。,路径上边的数目称作路径长度。,简单路径：,0 1 3 0 1 2,回 路：,例：,0 1 3 2,0 1 3 0,非简单路径：,非简单回路：,0 1 3 2 1 0,若图G中任意两个顶点之间都有路径相通，则称此图为连通图;,若无向图为非连通图，则图中各个极大连通子图，称作图的连通分量.,非连通图,连通图,A,B,C,D,E,F,G,
6、I,J,L,H,M,K,F,G,I,J,L,K,无向图G3,无向图 G3 的 3 个连通分量,若任意两个顶点之间都存在相互可通的有向路径，则称此有向图为强连通图.,对有向图，,否则，其各个强连通子图称作它的强连通分量。,强连通图,非强连通图,假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。,对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。,极小连通子图意思是： 该子图是 G 的连通子图，在该子图中删除任何一 条边，子图不再连通。,生成树,若 T 是 G 的生成树, 当且仅当 T 满足如下条件
7、: (1) T 是 G 的连通子图 (2) T 包含 G 的所有顶点 (3) T 中无回路,注：在生成树中添加一条边之后，必定会形成回路或环。,7.2 图的存储结构,一、图的数组（邻接矩阵）表示,二、图的邻接表存储表示,三、有向图的十字链表存储表示,7.2.1 邻接矩阵,定义矩阵的元素为,（1）无向图邻接矩阵是对称矩阵，同一条边 表示了两次； （2）顶点v 的度：等于二维数组对应行（或 列）中 1 的个数； （3）判断两顶点v、u 是否为邻接点：只需判 二维数组对应分量是否为 1； （4） G占用存储空间只与它的顶点数有关， 与边数无关 ；适用于边稠密的图。,无向图邻接矩阵表示的特点：,有向图
8、的邻接矩阵一般为非对称矩阵。,b,网的邻接矩阵表示：,typedef struct ArcCell / 矩阵元素的定义（边或弧的信息） VRType adj; / VRType是顶点关系类型. / 对无权图，用1或0表示相邻否 / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMaxVertexNum MaxVertexNum;,typedef struct / 图的定义 VertexType vexsMaxVertexNum; /顶点向量 AdjMatrix edges; /邻接矩阵 int vexnum, edgenu
9、m; / 顶点数，边或弧数 MGraph;,设 G 是 MGraph 类型的变量，用于存储无 向图，该图有 n 个顶点，e 条边。 G 的存储图 示如下：,二、图的邻接表存储表示,有向图的邻接表,在有向图的邻接表中不易找到指向该顶点的弧。,有向图的逆邻接表,在有向图的逆邻接表中，对每个顶点链接的是指向该顶点的弧,typedef struct ArcNode / 链表结点 int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *next; / 指向下一条弧的指针 EdgeNode;,adjvex next,弧的结点结构,typedef struct VertexNod
10、e / 表头结点 VertexType data; / 顶点信息 ArcNode *firstedge; / 指向第一条依附该顶点的弧 VertexNode, AdjListMaxVertexNum;,顶点的结点结构,typedef struct ALGraph / 图结构 AdjList adjlist; / 顶点数组 int vexnum, edgenum; / 顶点数、弧数 ALGraph;,图的结构定义(邻接表),将有向图的邻接表和逆邻接表结合在一起的一种图的链式存储结构。,三、有向图的十字链表存储表示,弧结点结构链表结点,指向下一个有相同弧尾的结点,指向下一个有相同弧头的结点,typ
11、edef struct ArcBox / 弧的结构表示 int tailvex, headvex; struct ArcBox *hlink, *tlink; InfoType *info; ,tailvex,headvex,hlink,tlink,info,顶点结点结构顺序表元素,指向该顶点的第一条入弧,指向该顶点的第一条出弧,typedef struct VexNode / 顶点结构表示 VertexType data; ArcBox *firstin, *firstout; ,data,firstin,firstout,(a) 顶点结点结构,(b) 弧结点结构,typedef struc
12、t OLGraph VexNode xlistMaxVertexNum; / 顶点结点(表头向量) int vexnum, edgenum; /有向图的当前顶点数和弧数 OLGraph;,有向图的十字链表结构表示,7.3 图 的 遍 历及图的连通分量,从图中某个顶点出发游历图，访遍 图中其余顶点，并且使图中的每个顶点 仅被访问一次的过程。,深度优先搜索,广度优先搜索,从图中某个顶点V0 出发，访问此顶点,然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。,一、深度优先搜索（DFS）遍历图,连通图的深度优先搜索遍历,深度优先搜索( DFS
13、),基本思想：仿树的先序遍历过程。,Depth_First Search,v1,DFS 结果,例1：,v2,v4,v8,v5,v3,v6,v7,例2：,v2 v1 v3 v5 ,DFS 结果,v4 v6,起点,起点,例 ：图 G 中，以 V1 起点的的深度优先序列： （1） V1,V2,V4,V5,V8,V3,V6,V7, （2） V1,V2,V5,V8,V4,V3,V6,V7,由于没有规定 访问邻接点的顺序， 深度优先序列不是唯一的,从上页的图解可见:,1. 从深度优先搜索遍历连通图的过程类似于树的先根遍历;,解决的办法是：为每个顶点设立一个 “访问标志 visitedw”;,2. 如何判别
14、V的邻接点是否被访问？,void DFS(Graph G, int v) / 从顶点v出发，深度优先搜索遍历连通图 G visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w / 递归调用DFS / DFS算法7.4,DFS 结果,邻接矩阵 A,辅助数组 visited n ,起点,v2v1v3v5v4v6,例：,在图的邻接矩阵中如何进行DFS？,在图的邻接表中如何进行DFS？,v0 v1 v2 v3,D
15、FS 结果,辅助数组 visited n ,例：, 照样借用 visited n ！,起点,0 1 2 3,注意：在邻接表中，并非每个链表元素（表结点）都被扫描到,遍历速度很快。,void DFSTraverse(Graph G) / 对图 G 作深度优先遍历 算法7.5 int v; for (v=0; v G.vexnum; + v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFS（算法7.4） ,DFS 算法效率分析:,（设图中有 n 个顶点，e 条边） 如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。 如果用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。,结论： 稠密图适于在邻接矩阵上进行深度遍历； 稀疏图（e n log n）适于在邻接表上进行深度遍历。,首先将图中每
