数据结构课件：第7章图

1、第7章 图第 2 页7.1 图的术语与定义图的定义图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对。图的分类 有向图 无向图第 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 = , , , , , , EACBD第

2、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) V0V4V3V1V2第 7 页7.1 图的术语与定义例如： G2 = V2 = v0，v1，v2，v3 E2 = , , , 例245136G1图G1中：V(G1

3、) = 1 , 2 , 3 , 4 , 5, 6 E(G1) = , , , , , , V0 V1 V2 V3第 8 页7.1 图的术语与定义图的应用举例例1、交通图（公路、铁路） 顶点：地点边：连接地点的路例2、电路图 顶点：元件边：连接元件之间的线路例3、通讯线路图 顶点：地点边：地点间的连线例4、各种流程图如产品的生产流程图。 顶点：工序边：各道工序之间的顺序关系第 9 页7.1 图的术语与定义图的基本术语1 邻接点及关联边 邻接点：边的两个顶点 关联边：若边e= (v, u), 则称顶点v、u 关连边e2 顶点的度、入度、出度 顶点V的度 = 与V相关联的边的数目 在有向图中： 顶点

4、V的出度 = 以V为起点有向边数 顶点V的入度 = 以V为终点有向边数 顶点V的度 = V的出度+V的入度 设图G 的顶点数为 n，边数为 e 图的所有顶点的度数和 = 2*e （每条边对图的所有顶点的度数和“贡献”2度） V0 V4 V3 V1 V2eV0V1V2V3第 10 页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，则称该序列为回路。有向图 D =（V，E）中的顶点序列 v1, v2, , vk，若 E (i=

5、1,2,k-1)，v=v1，u=vk，则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路。第 11 页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 V0 V4 V3 V1 V2V0V1V2V3第 12 页7.1 图的术语与定义连通图（强连通图） 在无（有）向图 G= 中，若对任何两个顶点 v、u 都存在从 v 到 u 的路径，则称G是连通图（强连通图） 非连通图

6、 连通图 强连通图 非强连通图 V0 V1 V2 V3 V0 V4 V3 V1 V2 V0 V1 V2 V3 V0 V2 V3 V1 V5 V4第 13 页7.1 图的术语与定义子图 设有两个图 G=（V，E），G1=（V1，E1），若V1 V，E1 E，E1关联的顶点都在 V1 中，则称 G1 是 G 的子图；例 (b)、(c) 是 (a) 的子图(a)(b)(c) V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2第 14 页7.1 图的术语与定义连通分图（强连通分量） 无向图G的极大连通子图称为G的连通分量。 极大连通子图意思是：该子图是G连通子图，

7、将G的任何不在该子图中的顶点加入，子图不再连通。连通分图非连通图 V0 V2 V3 V1 V5 V4第 15 页7.1 图的术语与定义连通分图（强连通分量） 有向图D的极大强连通子图称为D的强连通分量。 极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。强连通分量 V0 V1 V2 V3 V0 V2 V3 V1第 16 页7.1 图的术语与定义生成树 包含无向图 G 所有顶点的极小连通子图称为G生成树。 极小连通子图意思是：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通，若T是G的生成树当且仅当T满足如下条件： T是G的连通子图 T

8、包含G的所有顶点 T中无回路连通图G1G1的生成树 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2第 17 页 V0 V1 V2 V37.2 图的存储结构一、数组表示法（邻接矩阵表示） 邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：Aij=1 若(vi,vj)E 或 E0 否则0 1 0 1 00 1 0 10 1 0 1 10 1 0 00 1 1 0 0在数组表示法中，用邻接矩阵表示顶点间的关系 V0 V4 V3 V1 V20 1 1 00 0 0 00 0 0 10 0 0第 18 页7.2 图的存储结构二、邻接表邻接表是图的链式存储结构1、无向图的邻接表 顶点：通常按编号

9、顺序将顶点数据存储在一维数组中； 关联同一顶点的边：用线性链表存储。 V0 V4 V3 V1 V22 0 1 2 3 4m-1V0V1V2V3V413422110034该结点表示边(V2,V4)，其中的4是V4在一维数组中的位置第 19 页7.2 图的存储结构结点typedef struct ArcNode int adjvex; / 邻接点域，/ 存放与Vi邻接的点在表头数组中的位置 struct ArcNode *next; / 链域，下一条边或弧 ArcNode;表头结点typedef struct tnode VertexType vexdata; / 存放顶点信息 ArcNode *

10、 firstarc; / 指向第一个邻接点 VNode, AdjList MAX_VERTEX_NUM ;typedef struct AdjList vertices; int vexnum, arcnum; / 顶点数和弧数int kind; / 图的种类adjvex nextvexdata firstarc第 20 页7.2 图的存储结构无向图的邻接表的特点 1）在G邻接表中，同一条边对应两个结点； 2）顶点v的度：等于v对应线性链表的长度； 3）判定两顶点v ，u是否邻接：要看v对应线性链表中有无对应的结点。 4）在G中增减边：要在两个单链表插入、删除结点； 5）设存储顶点的一维数组大

11、小为 m（m图的顶点数n），图的边数为 e，G占用存储空间为：m+2*e。G占用存储空间与G的顶点数、边数均有关；适用于边稀疏的图。第 21 页7.2 图的存储结构二、邻接表2、有向图的邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为起点的弧：用线性链表存储1234v0v2v3v1vexdatafirstarc 3 2 4 1adjvexnext类似于无向图的邻接表，所不同的是：以同一顶点为起点的弧：用线性链表存储V0V1V2V3第 22 页7.2 图的存储结构二、邻接表3、有向图的逆邻接表顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储。1234v0v2v3v1ve

12、xdatafirstarc 4 1 1 3类似于有向图的邻接表，所不同的是：以同一顶点为终点弧：用线性链表存储V0V1V2V3第 23 页7.2 图的存储结构三、有向图的十字链表表示法弧结点：typedef struct ArcBox int tailvex, headvex; /弧尾、弧头在表头数组中位置 struct arcnode *hlink；/指向弧头相同的下一条弧 struct arcnode *tlink; /指向弧尾相同的下一条弧 ArcBox;tailvex headvex hlink tlink顶点结点：typedef struct VexNode VertexType d

13、ata; /存与顶点有关信息 ArcBox *firstin；/指向以该顶点为弧头的第一个弧结点 ArcBox *firstout; /指向以该顶点为弧尾的第一个弧结点 VexNode;VexNode OLGraphM;data firstin firstout第 24 页7.2 图的存储结构三、有向图的十字链表表示法例bdacab cd1234 1 3 1 2 3 4 3 1 4 3 4 2 4 1相同弧尾相同弧头第 25 页7.2 图的存储结构四、无向图的邻接多重表表示法顶点结点：typedef struct VexBox VertexType data; /存与顶点有关的信息 EBox

14、* firstedge; /指向第一条依附于该顶点的边 VexBox;VexBox AMLGraphM;data firstedge边结点：typedef struct EBox VisitIf mark; /标志域，记录是否已经搜索过 int ivex, jvex; /该边依附的两个顶点在表头数组中位置 struct EBox * ilink, * jlink; /分别指向依附于ivex和jvex的下一条边 EBox;mark ivex ilink jvex jlink第 26 页7.2 图的存储结构四、无向图的邻接多重表表示法例aecbd1234acdb5e 1 2 1 4 3 4 3 2

15、 3 5 5 2第 27 页7.3 图的遍历连通图的深度遍历（DFS）从图中某顶点v出发： 1）访问顶点v； 2）对v的每个未被访问的邻接点wj，从wj出发，继续对图进行深度优先遍历。深度遍历： V1,V2,V4,V5,V8,V3,V6,V7 例 V1 V8 V7 V6 V5 V4 V3 V2 V1 V2 V4 V3 V8 V7 V6 V5深度遍历： V1,V3,V6,V7,V2,V5,V8,V4第 28 页7.3 图的遍历图的深度遍历（DFS）Vw1SG1SG2SG3w2w3w2 W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。访问顶点

16、 V ：for (W1、W2、W3 ) 若该邻接点W未被访问， 则从它出发进行深度优先搜索遍历。第 29 页7.3 图的遍历图的深度遍历（DFS）Vw1SG1SG2SG3w2w3w2从图解可见：1. 从深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点设立一个 “访问标志 visitedw”。2. 如何判别V的邻接点是否被访问？第 30 页7.3 图的遍历Boolean visitedMAX; / 访问标志数组Status (*VisitFunc)(int v); / 访问函数void DFS ( Graph G, int v) / 从顶点v出发，深度优先搜索遍历连通图

17、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第 31 页7.3 图的遍历非连通图的深度优先搜索遍历 首先将图中每个顶点的访问标志设为 FALSE，之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。第 32 页7.3 图的遍历void DFSTraverse ( Graph G, Status (*V

18、isit) (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第 33 页7.3 图的遍历例如：abchdekfgF F F F F F F F FTTTTTTTTTachdkfe bgachkfedbg访问标志:访问次序:0 1 2 3 4 5 6 7 8第 34 页7.3 图的遍历图的深度遍历（DFS）算法7

19、.4和7.5开始访问V，置标志求V邻接点有邻接点w求下一邻接点W访问过结束NYNYDFS(G,w)开始标志数组初始化V=0V访问过?DFS(g,v)V=V+1VVexNum结束NYYN第 35 页7.3 图的遍历图的深度遍历（DFS）递归算法V1V2V4V5V3V7V6V8例12341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 8 2678678 7深度遍历：V1V3 V7 V6 V2 V4 V8 V5第 36 页7.3 图的遍历图的广度遍历（BFS） 从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发

20、，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V5 V6 V7 V8第 37 页7.3 图的遍历图的广度遍历（BFS） 从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访

21、问到为止。第 38 页7.3 图的遍历图的广度遍历（BFS）从图中某顶点v出发：1) 访问顶点v2) 访问v的所有未被访问的邻接点w1,w2,wk3) 依次从这些邻接点出发，访问它们的所有未被访问的邻接点，直到图中所有访问过的顶点的邻接点都被访问到。V1V8V7V6V5V4V3V2V1 V2 V4 V3 V8 V7 V6 V5V1,V2,V3,V4,V8,V5,V6,V7V1,V3,V2,V6,V7,V4,V5,V8第 39 页7.3 图的遍历void BFSTraverse ( Graph G, Status (*Visit) (int v) ) for ( v=0; vG.vexnum;

22、+v ) visitedv = FALSE; / 初始化访问标志 InitQueue(Q); / 置空的辅助队列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未访问 / BFSTraverse第 40 页7.3 图的遍历visitedv = TRUE; Visit(v); / 访问vEnQueue(Q, v); / v入队列while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为u for ( w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w) ) if (

23、! visitedw ) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 访问的顶点w入队列 / if / while第 41 页7.3 图的遍历图的广度遍历（BFS）例1423512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍历序列：10 1 2 3 4 54fr遍历序列：1 40 1 2 3 4 54 3fr遍历序列：1 4 3第 42 页7.3 图的遍历图的广度遍历（BFS）例142350 1 2 3 4 54 3 2fr遍历序列：1 4 3 20 1

24、2 3 4 5 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍历序列：1 4 3 2 512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 2第 43 页7.3 图的遍历图的广度遍历（BFS）例142350 1 2 3 4 5 2 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 fr遍历序列：1 4 3 2 512341342vexdatafirstarc 5 5 4 3adjvexnext55 1 5 1 1 4 3 2 2第 44

25、页7.4 图的最小生成树问题提出要在n个城市间建立通信联络网，顶点表示城市权城市间建立通信线路所需花费代价希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小最小代价生成树问题分析n个城市间，最多可设置 n(n-1)/2 条线路。n个城市间建立通信网，只需 n-1 条线路。问题转化为：如何在可能的线路中选择 n-1 条，能把所有城市（顶点）均连起来，且总耗费（各边权值之和）最小。第 45 页7.4 图的最小生成树普里姆算法的基本思想 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。 在添加的顶点 w 和已经在生成树上的顶点 v 之间必定存在一

26、条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。 之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。第 46 页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；（4）重复(2)(3)，直到 U=V 为止；UV-UvuU扩大V-U缩小vu第 47 页7.4 图的最小生成树普里姆算法（Prim）教材P175

27、V3V1V4V6V5V23652165546V3V1V4V6V5V212V3V1V4V6V5V214V3V1V4V6V5V2142V3V1V4V6V5V21452V3V1V4V6V5V21453U= V1 U= V1,V3 U= V1,V3,V6U= V1,V3,V6,V4 U= V1,V3,V6,V4,V2 U= V1,V3,V6,V4,V2,V5 第 48 页7.4 图的最小生成树普里姆算法的基本思想 设置一个辅助数组，对当前 V-U 集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：struct VertexType adjvex; / U集中的顶点序号 VRType lowco

28、st; / 边的权值 closedge MAX_VERTEX_NUM ;第 49 页7.4 图的最小生成树普里姆算法的基本思想有关数据的存储结构 无向连通网络: MGraph G 选择权值最小的边： 设置一个一维数组closedge ，对 vV-U closedgev.lowcost = min costu,v| uU /保存连接v到U中各顶点权最小边的权值closedgev.adjvex = u/用来记录该边在U中的顶点第 50 页7.4 图的最小生成树普里姆算法的基本思想V3V1V4V6V5V23652165546 v1 v1 v1 0 6 1 5Closedgeadjvexlowcost

29、 0 1 2 3 4 5 6Closedgeadjvexlowcost 0 1 2 3 4 5 6 v3 v1 v3 v30 5 0 5 6 4U= v1 U= v1,v3 V3V1V4V6V5V23652165546UU第 51 页7.4 图的最小生成树普里姆算法的基本思想 v1 v1 v10 6 1 5adjvexlowcostv1 v3 v1 v3 v30 5 0 5 6 4adjvexlowcostv1,v3 v20 0 0 0 3 0adjvexlowcostv1,v3,v6,v4,v20 0 0 0 0 0adjvexlowcostv1,v3,v6,v4,v2,v5iclosedg

30、e 0 1 2 3 4 5 Uadjvexlowcostv1,v3,v6 v3 v6 v30 5 0 2 6 0adjvexlowcostv1,v3,v6,v4 v3 v30 5 0 0 6 0第 52 页7.4 图的最小生成树void MiniSpanTree_P ( MGraph G, VertexType u ) /用普里姆算法从顶点u出发构造网G的最小生成树 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 辅助数组初始化 if ( j!=k ) closedge j = u, G.arcs k j .adj ; / 从u点开始初

31、始化 adjvex,lowcost closedgek.lowcost = 0; / 初始，Uu for (i=0; iG.vexnum; +i) 继续向生成树上添加顶点; /MiniSpanTree第 53 页7.4 图的最小生成树 k = minimum(closedge); / 求出加入生成树的下一个顶点(k) printf ( closedgek.adjvex, G.vexsk );/ 输出生成树上一条边 closedgek.lowcost = 0; / 第k顶点并入U集 for ( j=0; jG.vexnum; +j ) / 修改其它顶点的最小边 if ( G.arcskj.adj

32、 closedgej.lowcost ) closedge j = G.vexsk, G.arcskj.adj ; 第 54 页7.4 图的最小生成树克鲁斯卡尔(Kruskal)算法 考虑问题的出发点：为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。 具体做法：先构造一个只含 n 个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG 上加上这条边，如此重复，直至加上n-1条边为止。第 55 页7.4 图的最小生成树克鲁斯卡尔(Kruskal)算法设连通网 N = ( V, E )。令最小生成树初始状态为只有 n 个顶点而无边的非连通图 T

33、= (V, )，每个顶点自成一个连通分量。在E中选取代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入到 T中；否则，舍去此边，选取下一条代价最小的边。依此类推，直至T中所有顶点都在同一连通分量上为止。第 56 页7.4 图的最小生成树克鲁斯卡尔(Kruskal)算法V3V1V4V6V5V2365216554616543212345第 57 页7.4 图的最小生成树构造非连通图 ST=( V, );k = i = 0; / k 计选中的边数while (kn-1) +i; 检查边集 E 中第 i 条权值最小的边(u,v); 若(u,v)加入ST后不使ST中产生回路， 则 输出边(u,v); 且 k+;第 58 页7.4 图的最小生成树克鲁斯卡尔(Kruskal)算法V3V1V4V6V5V2365216554616543212345datajihe124536124536124536vexhweight1122132335