数据结构和算法设计-第7章_图11-03

第7章 图,第 2 页,7.1 图的术语与定义,图的定义图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对。图的分类 有向图: All arcs are directed 无向图：All arcs are undirected,第 3 页,7.1 图的术语与定义,图的定义有向图有向图G是由两个集合V(G)和E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v、w是顶点，v为弧尾，w为弧头。,第 4 页,7.1 图的术语与定义,例如： G1 = V1 = A, B, C, D, E E1 = , , , , , , ,E,A,C,B,D,第 5 页,7.1 图的术语与定义,图的定义无向图无向图G是由两个集合V(G)和E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是边的有限集合，边是顶点的无序对，记为 (v,w) 或 (w,v)，并且(v,w)=(w,v)。,第 6 页,7.1 图的术语与定义,例如： G2 = V2 = v0 ,v1,v2,v3,v4 E2 = (v0,v1), (v0,v3), (v1,v2), (v1,v4), (v2,v3), (v2,v4) ,V0,V4,V3,V1,V2,第 7 页,7.1 图的术语与定义,例如： G2 = V2 = v0，v1，v2，v3 E2 = , , , ,V(G1) = 1 , 2 , 3 , 4 , 5, 6 E(G1) = , , , , , , ,第 8 页,7.1 图的术语与定义,图的应用举例例1、交通图（公路、铁路） 顶点：地点边：连接地点的路例2、电路图 顶点：元件边：连接元件之间的线路例3、通讯线路图 顶点：地点边：地点间的连线例4、各种流程图如产品的生产流程图。 顶点：工序边：各道工序之间的顺序关系,第 9 页,7.1 图的术语与定义,图的基本术语1 邻接点及关联边 邻接点：边的两个顶点 关联边：若边e= (v, u), 则称顶点v、u 关联边e2 顶点的度、入度、出度 顶点V的度 = 与V相关联的边的数目 在有向图中： 顶点V的出度OD = 以V为起点有向边数 顶点V的入度ID = 以V为终点有向边数 顶点V的度Degree = V的出度+V的入度 设图G 的顶点数为 n，边数为 e 图的所有顶点的度数和 = 2*e （每条边对图的所有顶点的度数和“贡献”2度）,e,第 10 页,举例,A,C,D,F,E,例如:,TD(B) = 3,TD(A) = 2,B,A,B,E,C,F,例如:,ID(B) = 2,OD(B) = 1,TD(B) = 3,第 11 页,7.1 图的术语与定义,路径、回路 无向图 G =（V，E）中的顶点序列v1, v2, ,vk，若 (vi,vi+1)E ( i=1, 2 , k-1)， v=v1, u=vk，则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路。 有向图 DG =（V，E）中的顶点序列 v1, v2, , vk，若 E (i=1,2,k-1)，v=v1，u=vk，则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路。,第 12 页,例:长度为3的路径是？,简单路径:序列中顶点不重复出现的路径。,简单回路:序列中第一个顶点和最后一个顶点相同的路径。,A,B,E,C,F,(A-F),第 13 页,7.1 图的术语与定义,例如 在图G1中，V0, V1, V2, V3 是 V0 到 V3 的路径；V0, V1, V2, V3, V0 是回路。 在图G2中，V0, V2, V3 是 V0 到 V3 的路径； V0, V2, V3, V0 是回路。,无向图G1,有向图G2,第 14 页,7.1 图的术语与定义,连通图（connected Graph）（强连通图） 在无（有）向图 G= 中，若对任何两个顶点 v、u 都存在从 v 到 u 的路径，则称G是连通图（强连通图，strong connected）,非连通图,连通图,强连通图,非强连通图,没有V1到V0的路径,第 15 页,7.1 图的术语与定义,子图(sub-Graph) 设有两个图 G =（V，E），G1 =（V1，E1），若V1 V，E1 E，E1关联的顶点都在 V1 中，则称 G1 是 G 的子图；例 (b)、(c)、(d) 是 (a) 的子图,(a),(b),(c),(d),第 16 页,7.1 图的术语与定义,连通分量（connected component） 无向图G的极大连通子图称为G的连通分量。 极大连通子图含义：该子图F是G的连通子图，将G的任何不在该子图F中的顶点加入，构成的子图将不再连通。看图7.3的例子,连通分量,非连通图,第 17 页,7.1 图的术语与定义,强连通分量（strong connected component） 有向图D的极大强连通子图称为D的强连通分量。 极大强连通子图的含义：该子图F是D的强连通子图，将D的任何不在该子图F中的顶点加入，构成的子图将不再是强连通的。,将V1加入后不再连通,第 18 页,7.1 图的术语与定义,生成树 包含无向图 G 的所有顶点的极小（最少数目的边）连通子图称为G的生成树。 极小连通子图 的含义：该子图是G的连通子图且包含G的全部顶点，在该子图中删除任何一条边，子图将不再连通，若T是G的生成树当且仅当(if and only if)T满足如下条件： T是G的连通子图 T包含G的所有顶点 T中无回路,连通图G1,G1的生成树,第 19 页,或者说：一个连通图的生成树，是指一个极小连通子图，它含有图中的全部顶点，且以最少的边数(n-1条)使其连通。如增加一条边必构成一个环。有n个顶点的连通图，其生成树是由n个顶点和n-1条边组成的连通子图，如图C.,(a)无向图G (b) G的连通分量G1 (c)G1的一棵生成树,第 20 页,生成树的理解要点,如果在生成树上添加一条边，必定构成一个环，因为这条边依附的那两个顶点之间有了第二条路径；一棵有n个顶点的生成树有且仅有n-1条边，如果一个图有n个顶点和小于n-1条边，则是非连通图（存在孤立顶点）。如果它多于n-1条边，则一定有环；但是n-1条边的图不一定是生成树(why?)。,因为可能存在回路,第 21 页,生成树的特点,一个图可以有许多棵不同的生成树，所有生成树具有如下特点：1、生成树的顶点个数与图的顶点个数相同；2、生成树是图的极小连通子图；3、一个有n个顶点的连通图的生成树有n-1条边；4、生成树中任意两个顶点之间的路径唯一；5、在生成树中添加一条边必然形成回路；6、含n个顶点n-1条边的图不一定是生成树。,第 22 页,7.2 图的存储结构,一、图的数组(邻接矩阵)存储表示,二、图的邻接表存储表示,第 23 页,7.2 图的存储结构,一、数组表示法（邻接矩阵表示） 邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：,在数组表示法中，用邻接矩阵表示顶点间的关系,值得注意：对无向图，邻接矩阵中非零元素的个数等于图的边数乘以2；对有向图，邻接矩阵中非零元素的个数等于边(箭线)的个数。,第 24 页,第 25 页,Aij=,wij 若vi, vj 间有弧(边)，且权值为wij,0 当vi, vj 间无弧或边时,对于带权图，邻接矩阵定义为：,A,B,E,C,F,A B C E F,A BCEF,6,1,3,8,2,9,5,第 26 页,邻接矩阵类型定义,#define MAX_VERTEX_NUM 20Typedef enumDG, DN, UDG, UDNGraphKind; / 有向图，有向网，无向图，无向网typedef struct ArcCell / 弧的定义, 结构数组 VRType adj; / VRType是顶点关系类型 / 对无权图，用1或0表示相邻否 / 对带权图，则用权值或0表示相邻否 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;,第 27 页,邻接矩阵类型定义,上述定义中，ArcCell是结构类型, AdjMatrix是（二维数组）矩阵类型typedef struct / 图的定义 VertexType / VertexType为顶点类型，can be int or char etc. vexsMAX_VERTEX_NUM; /顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数，弧数 GraphKind kind; / 图的种类标志 MGraph;,第 28 页,Graph G：,第 29 页,无向图数组表示法特点,1、无向图的邻接矩阵为对称矩阵(若(vi, vj)VR则 (vj, vi)VR), 只需存储其下三角;2、判断任意两个顶点是否为邻接点(ai,j=1 or 0)；3、对无向图，易于计算顶点vi的度(how to calculate?),第 30 页,7.2 图的存储结构,二、邻接表：图的链式存储结构1、无向图的邻接表 顶点：通常按编号顺序将顶点数据存储在一维数组中； 关联同一顶点的边：用线性链表存储(约定下标由小到大)。,该结点表示边(V2,V4)，其中的4是V4在一维数组中的位置,第 31 页,7.2 图的存储结构,链表结点（弧结点）typedef struct ArcNode int adjvex; / 顶点的邻接点域 / 存放与Vi邻接的点在表头数组中的位置 struct ArcNode *next; / 链域，下一条边或弧 ArcNode;表头结点typedef struct tnode int vexdata; / 存放顶点数据信息 ArcNode * firstarc; / 指向ArcNode类型的第一个链表结点 VNode, AdjList MAX_VERTEX_NUM ;typedef struct AdjList vertices; /结构数组int vexnum, arcnum; / 顶点数和弧数int kind; / 图的种类ALGraph;,第 32 页,7.2 图的存储结构,无向图的邻接表的特点 1）在G邻接表中，同一条边对应两个结点； 2）顶点v的度：等于v对应线性链表的长度； 3）判定两顶点v ，u是否邻接：要看v对应线性链表中有无对应的结点u。 4）在G中增减边：要在两个相邻顶点关联的单链表中插入、删除结点； 5）设存储顶点的一维数组大小为 m（m图的顶点数n），图的边数为 e，G占用存储空间为：m+2*e（精确地应考虑数据类型）。G占用存储空间与G的顶点数、边数均有关；适用于边稀疏的图。,第 33 页,7.2 图的存储结构,2、有向图的邻接表顶点：用一维数组存储（按编号升序排列）以同一顶点为起点的弧：用线性链表存储,adjvex,next,类似于无向图的邻接表，所不同的是：以同一顶点为起点的弧：用线性链表存储,第 34 页,7.2 图的存储结构,3、有向图的逆邻接表顶点：用一维数组存储（按编号升序排列）以同一顶点为终点的弧：用线性链表存储。,类似于有向图的邻接表，所不同的是：以同一顶点为终点的弧：用线性链表存储,第 35 页,7.3 图的遍历,深度优先遍历广度优先遍历,第 36 页,7.3 图的遍历,连通图的深度遍历（DFS）从图中某顶点v出发： 1）访问顶点v； 2）对v的每个未被访问的邻接点wj，从wj出发，继续对图进行深度优先遍历。,深度遍历： V1,V2,V4,V5,V8,V3,V6,V7,例,深度遍历： V1,V3,V6,V7,V2,V5,V8,V4,第 37 页,7.3 图的遍历,图的深度遍历（DFS）,V,w1,SG1,SG2,SG3,w2,w3,w2,W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,访问顶点 V ：for (W1、W2、W3 ) 若该邻接点Wi(i=1,2,3)未被访问， 则从它出发进行深度优先搜索遍历。,第 38 页,7.3 图的遍历,图的深度遍历（DFS）,V,w1,SG1,SG2,SG3,w2,w3,w2,从图解可见：,1. 从深度优先搜索遍历连通图的过程看，DFS类似于树的先根遍历；,解决的办法是：为每个顶点设立一个 “访问标志 visitedw”。,2. 如何判别V的邻接点是否被访问？,第 39 页,7.3 图的遍历,Boolean visitedMAX; / 访问标志数组Status (*VisitFunc)(int v); / 访问函数,can be printfvoid 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,第 40 页,7.3 图的遍历,非连通图的深度优先搜索遍历 首先将图中每个顶点的访问标志设为 FALSE，之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。,第 41 页,7.3 图的遍历,void DFSTraverse ( Graph G, Status (*Visit) (int v) / 对非连通图 G 作深度优先遍历。 VisitFunc = Visit; /函数入口地址给函数指针 for ( v=0; vG.vexnum; +v ) visitedv = FALSE; / 访问标志数组初始化 for ( v=0; vG.vexnum; +v ) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFS,第 42 页,7.3 图的遍历,例如：,a,b,c,h,d,e,k,f,g,F F F F F F F F F,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b,g,a,c,h,k,f,e,d,b,g,访问标志:,访问次序:,a b c d e f g h k,0 1 2 3 4 5 6 7 8,第 43 页,7.3 图的遍历,图的深度遍历（DFS）算法7.4和7.5,开始,访问V，置标志,求V邻接点,有邻接点w,求下一邻接点,W访问过,结束,N,Y,N,Y,DFS(G,w),开始,标志数组初始化,V=0,V访问过?,DFS(g,v),V=V+1,VVexNum,结束,N,Y,Y,N,第 44 页,7.3 图的遍历,图的深度遍历（DFS）递归算法,深度遍历：V1,V3 ,V7 ,V6 ,V2 ,V4 ,V8 ,V5,第 45 页,7.3 图的遍历,图的广度遍历（BFS） 从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,第 46 页,7.3 图的遍历,图的广度遍历（BFS） 从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。,若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。,第 47 页,7.3 图的遍历,图的广度遍历（BFS）从图中某顶点v出发：1) 访问顶点v2) 访问v的所有未被访问的邻接点w1,w2,wk3) 依次从这些邻接点出发，访问它们的所有未被访问的邻接点，直到图中所有访问过的顶点的邻接点都被访问到。,V1,V2,V3,V4,V8,V5,V6,V7,V1,V3,V2,V6,V7,V4,V5,V8,第 48 页,7.3 图的遍历,void BFSTraverse ( Graph G, Status (*Visit) (int v) ) for ( v=0; vG.vexnum; +v ) visitedv = FALSE; / 初始化访问标志 InitQueue(Q); / 置空的辅助队列Q for ( v=0; v=0; w=NextAdjVex(G,u,w) ) if ( ! visitedw ) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 访问的顶点w入队列 / if / while,第 50 页,7.3 图的遍历,图的广度遍历（BFS）,第 51 页,7.3 图的遍历,图的广度遍历（BFS）,第 52 页,7.3 图的遍历,图的广度遍历（BFS）,第 53 页,7.4 图的最小生成树,问题提出要在n个城市间建立通信联络网：顶点表示城市；权城市间建立通信线路所需花费的代价；希望找到一棵生成树，使它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小此即最小代价生成树。问题分析n个城市间，最多可设置 n(n-1)/2 条线路，如全部布线代价太高；n个城市间建立通信网，只需 n-1 条线路即可。问题转化为：如何在可能的线路中选择 n-1 条，能把所有城市（顶点）均连起来，且总耗费（各边权值之和）最小。,第 54 页,问题分析：,可用连通图表示n个城市以及n个城市间可能的通信线路，其中图的顶点表示城市，便表示两城市之间的线路，边的权值表示该段线路的代价。对于n个顶点的连通图可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，要选择一棵生成树，使得总耗费最少。这就是构造连通图的最小代价生成树（Minimum Cost Spanning Tree，简称最小生成树MST）的问题。一棵生成树的代价就是树上各边的代价之和。构造图的最小生成树的两种算法：,第 55 页,7.4 图的最小生成树,Prim算法的基本思想： 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。 在添加的顶点 w 和已经在生成树上的顶点 v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。 之后继续往生成树上添加顶点，直至生成树上含有”n个顶点、n-1条边”为止。,第 56 页,7.4 图的最小生成树,普里姆算法（Prim）设 G=（V，GE）为一个具有 n 个顶点的连通网络，T=（U，TE）为构造的生成树。（1）初始时，U = u0，TE = ；（2）在所有 uU 、vV-U 的边（u,v）中选择一条权值最小的边，不妨设为（u,v）；（3）(u,v) 加入TE，同时将 v 加入U(注意这时U集合变大、V-U变小了，实际上是按照选择U集合与V-U集合关联的最小权的边，向U中添加顶点)；（4）重复(2)(3)，直到 U=V 为止；,U,V-U,v,u,U扩大,V-U缩小,v,u,第 57 页,7.4 图的最小生成树,普里姆算法（Prim）教材P175,U= V1 ,U= V1,V3 ,U= V1,V3,V6,U= V1,V3,V6,V4 ,U= V1,V3,V6,V4,V2 ,U= V1,V3,V6,V4,V2,V5 ,Question：从不同的顶点出发构造的最小生成树是否唯一？,第 58 页,7.4 图的最小生成树,克鲁斯卡尔(Kruskal)算法 考虑问题的出发点：为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,具体做法：先构造一个只含 n 个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG 中加上这条边，如此重复，直至加到n-1条边为止。,第 59 页,Kruskal算法的例子,（a）,（b）,（c）,（d）,（f）,（e）,第 60 页,7.4 图的最小生成树,克鲁斯卡尔(Kruskal)算法设连通网 N = ( V, E )。令最小生成树初始状态为只有 n 个顶点而无边的非连通图 T = (V, )，每个顶点自成一个连通分量。在E中选取代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入到 T中；否则，舍去此边，选取下一条代价最小的边。依此类推，直至T中