数据结构第5章 图.ppt

1、第5章 图 （一）课程内容 5.1 图的概念 5.2 图的存储结构 5.3 图的遍历 5.4 生成树和最小生成树 5.5 最短路径 5.6 拓扑排序 （二）学习目的与要求本章的目的图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法。 本章重点是掌握在图的两种存储结构上实现的遍历算法。 本章难点是图的应用算法：求最小生成树，求最短路径以及拓扑排序，只要求考生掌握这些算法的基本思想及时间性能。,（三）考核知识点与考核要求 1.图的概念，要求达到“领会”层次。1.1 图的逻辑结构特征。1.2 图的常用术语及含义。 2.图的存储结构，要求达到“简单应用”层次。2.1 邻接矩阵和邻接表这两种

2、存储结构的特点及适用范围。2.2 根据应用问题的特点和要求选择合适的存储结构。 3.图的遍历，要求达到“简单应用”层次。3.1连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法,其执行过程以及时间分析。3.2 确定两种遍历所得到的顶点访问序列。3.3 图的两种遍历与树的遍历之间的关系。3.4两种遍历所使用的辅助数据结构（栈或队列）在遍历过程中所起的作用。3.5 利用图的两种遍历设计算法解决简单的应用问题。,（三）考核知识点与考核要求 4.生成树和最小生成树，要求达到“领会”层次。4.1 生成树和最小生成树的概念。4.2 对遍历给定的图，画出深度优先和广度优先生成树或生成森林。4.3Pri

3、m和Kruskal算法的基本思想、时间性能及这两种算法各自的特点。4.4 要求对给定的连通图，根据Prim和Kruskal算法构造出最小生成树。 5.最短路径，要求达到“领会”层次。5.1 最短路径的含义。5.2 求单源最短路径的Dijkstra算法的基本思想和时间性能。5.3对于给定的有向图，根据Dijkstra算法画出求单源最短路径的过程示意图。 6.拓扑排序，要求达到“领会”层次。6.1 拓扑排序的基本思想和步骤。6.2 拓扑排序不成功的原因。6.3 对给定的有向图，若拓扑序列存在，则要求写出一个或多个拓扑序列。,5.1 图的概念 图(Graph)是一种复杂的非线性结构，在图结构中，对结

4、点的前驱和后继的个数没有任何限制，结点之间的关系是任意的，图中任意两个结点之间都可能有关系。图结构在计算机科学、人工智能、工程、数学、物理等领域中，有着广泛的应用。 一、图的二元组定义 定义：图G由两个集合V和E组成,记为：G=(V，E)其中：V是有限的非空集合，V中的元素称为顶点或结点，E是V中顶点偶对(vi,vj)的集合，E中的元素称为边。 说明：图G的顶点集和边集也可记为V(G)和E(G)。E(G)可以是空集，若为空，则图G只有顶点没有边；图中的边(vi,vj)描述了两个顶点之间是相关的。,二、无向图和有向图1、无向图：若图G中的每条边都是没有方向的，则称G为无向图。 无向图中边的表示：

5、无向图中的边均是顶点的无序对，无序对通常用圆括号表示，无序对(vi,vj)和(vj,vi) 表示图中的同一条边。 2、有向图：若图G中的每条边都是有方向的，则称G为有向图。 有向图中边的表示：有向图中的边是由顶点的有序对组成，有序对通常用尖括号表示，有序对和 表示的是图中不同的边。有向边也称为弧，边的始点称为弧尾，终点称为弧头。 说明：若(v1，v2)或是E(G)中的一条边，则要求v1v2；不允许一条边在图中重复出现； 不允许在同一个图中既有有向边又有无向边。,6,3、完全图无向完全图：若G是具有n个顶点e条边的无向图，则顶点数与边数的关系为0en(n-1)/2。把恰有n(n-1)/2条边的无

6、向图称为无向完全图。有向完全图：若G是具有n个顶点e条边的有向图，则顶点数与边数的关系为0en(n-1)。把恰有n(n-1)条边的有向图称为有向完全图。 说明：完全图具有最多的边数。任意一对顶点间均有边相连。 三、图的边和顶点的关系 1、无向边和顶点关系 若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接顶点，或称vi和vj相邻接；并称(vi,vj)依附或关联于顶点vi和vj，或称(vi,vj)与顶点vi和vj相关联。,2、有向边和顶点关系 若是一条有向边，则称顶点vi邻接到vj，顶点vj邻接于顶点vi；并称边关联于vi和vj或称与顶点vi和vj相关联。 3顶点的度无向图中顶点v的度：无

7、向图中顶点v的度是关联于该顶点的边的数目，记为D(v)。 有向图顶点v的入度：有向图中，以顶点v为终点的边的数目称为v的入度，记为ID(v)。有向图顶点v的出度：有向图中，以顶点v为始点的边的数目，称为v的出度，记为OD(v)有向图顶点v的度：有向图中，顶点v的度定义为该顶点的入度和出度之和，即D(v)=ID(v)+OD(v)。无论有向图还是无向图，顶点数n、边数e和度数之间有如下关系： 。,8,四、子图：设G=(V，E)是一个图，若V是V的子集，E是E的子集，且E中的边所关联的顶点均在V中，则G=(V，E)也是一个图，并称其为G的子图。 五、路径1、无向图的路径：在无向图G中，若存在一个顶点

8、序列vp,vi1,vi2,vim,vq，使得(vp,vi1),(vi1,vi2),(vim,vq)均属于E(G)，则称该序列为顶点vp到vq的一条路径。2、有向图的路径：在有向图G中，若存在一个顶点序列vp,vi1,vi2,vim,vq，使得有向边,均属于E(G) ，则称该序列为顶点vp到vq的一条路径。 3、路径长度：路径长度定义为该路径上边的数目。4、简单路径：若一条路径除两端顶点可以相同外，其余顶点均不相同，则称此路径为一条简单路径。,9,9,9,5、回路：起点和终点相同的路径称为回路。 6、简单回路或简单环：起点和终点相同的简单路径称为简单回路或简单环。 7、有根图和图的根：在一个有向

9、图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根。 六、连通图和连通分量1、顶点间的连通性：在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。2、连通图：若在无向图G中，任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图。 3、连通分量：无向图G的极大连通子图称为G的连通分量。 说明： 任何连通图的连通分量只有一个，即是其自身； 非连通的无向图有多个连通分量。,10,10,七、强连通图和强连通分量 1、强连通图： 有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则

10、称G是强连通图。 2、强连通分量：有向图的极大强连通子图称为G的强连通分量。 说明： 强连通图只有一个强连通分量，即是其自身； 非强连通的有向图有多个强连分量。 八、网络 若将图的每条边都赋上一个权，则称这种带权图为网络(Network)。 说明：权是表示两个顶点之间的距离、耗费等具有某种意义的数。,11,5.2 图的存储结构 图的存储表示方法很多，这里介绍两种最常用的方法。至于具体选择哪一种方法，主要取决于具体的应用和要施加的操作。 为了适合用C语言描述，以下假定顶点序号从0开始，即n个顶点图G顶点集是V(G)=v0,v1,vn-1。 一、图的邻接矩阵表示法1、图的邻接矩阵 设G=(V，E)

11、是具有n个顶点的图，则G的邻接矩阵是元素具有如下性质的n阶方阵： 2、图的邻接矩阵表示法： 用邻接矩阵表示顶点间的相邻关系； 用一个顺序表来存储顶点信息。,3、网络的邻接矩阵 若G是网络，则邻接矩阵可定义为： 其中：wij表示边上的权值；表示一个计算机允许的、大于所有边上权值的数。 4、图的邻接矩阵存储结构的描述#define VertexNum 20 /最大顶点数 typedef char VertexType;/顶点类型定义 typedef int EdgeType;/权值类型定义 typedef struct VertexType vexsVertexNum; /顶点表 EdgeType

12、 edgesVertexNumVertexNum;/邻接矩阵，可看作边表 int n,e;/图中当前的顶点数和边数 MGraph; 5、建立无向网络的算法,/*建立无向网络的算法：*/ void CreateMGraph(MGraph *G) /建立无向网(图)的邻接矩阵表示 int i,j,k,w; scanf(%d%d, ,二、图的邻接表表示法1、图的邻接表 对于图G中的每个顶点vi，把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表(Adjacency List)。 2、邻接表的结点结构 (1)表结点结构：邻接表中每个表结点均有两个域 邻接点域adjve

13、x,存放与vi相邻接的顶点vj的序号j；链域next,将邻接表的所有表结点链在一起。 注意：若要表示边上的信息(如权值)，则在表结点中还应增加一个数据域。 (2)头结点结构：顶点vi邻接表的头结点包含两个域 顶点域vertex,存放顶点vi的信息； 指针域firstedge,vi的邻接表的头指针。,3、无向图的邻接表 对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边。因此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。 注意：n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。 4、有向图的邻接表 对于有向图，vi的邻接表中每个表结点都对应于以vi为

14、始点射出的一条边。因此，将有向图的邻接表称为出边表。 注意：n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。5、有向图的逆邻接表 在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。 6、图的邻接表存储结构的描述 7、建立无向图的邻接表算法,15,15,15,15,15,图的邻接表存储结构的描述 typedef struct node/边表结点定义 int adjvex; /邻接点域 struct node *next; /链域 /若要表示边上的权，则应增加一个数据域 EdgeNode; ty

15、pedef struct vnode /顶点表结点定义 VertexType vertex; /顶点域 EdgeNode *firstedge;/边表头指针 VertexNode; typedef VertexNode AdjListVertexNum;/AdjList是邻接表类型 typedef struct/邻接表定义 AdjList adjlist;/邻接表 int n,e; /图中当前顶点数和边数 ALGraph;,建立无向图的邻接表算法void CreateALGraph(ALGraph *G) /建立无向图的邻接表表示 int i,j,k; EdgeNode *s; scanf(%

16、d%d,/将新结点*s插入顶点vj的边表头部 ,5.3 图的遍历 图的遍历：从图的某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问，这一过程称为图的遍历。它是许多图的算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。 注意： 由于图中任一顶点都可能和其它顶点相邻接，所以在遍历图时，访问了某顶点之后，有可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一向量visited0n-1，该向量的每个元素的初值均为0，如果访问了顶点Vi，就将visitedi置为1，这样便可通过visitedi的

17、值来标志顶点Vi是否被访问过。 以下假定遍历过程中访问顶点的操作是简单地输出顶点。,一、图的深度优先遍历 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)。 1、递归定义：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 说明：图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先

18、对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。,2、深度优先搜索的过程 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在

19、x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。,3、深度优先遍历的递归算法(DFS算法)邻接矩阵表示的深度优先遍历算法邻接表表示的深度优先搜索算法 4、深度优先遍历序列（DFS序列） 对图进行深度优先遍历，按访问结点的先后顺序得到的结点序列称为该图的深度优先遍历序列，简称DFS序列。 说明： 一个图的DFS序列不唯一。 按小号优先的原则（当一个结点有多个邻接点时，选择标号最小的进行搜索）， DFS序列是唯一的。 由邻接矩阵表示的深度优先遍历算法得到的D

20、FS序列是唯一的，而由邻接表表示的深度优先搜索算法得到的DFS序列与建表时的输入顺序有关。,19,邻接矩阵表示的深度优先遍历算法： int visitedVertexNum=0;/定义标志向量 void DFSM(MGraph *G,int i) /以vi为出发点进行搜索，设邻接矩阵是0,l矩阵 int j; printf(%4c,G-vexsi);/访问顶点vi visitedi=1; for(j=0;jn;j+) /依次搜索vi的邻接点 if(G-edgesij=1) /以vi为源点开始DFSM搜索 ,邻接表表示的深度优先遍历算法： int visitedVertexNum=0;/定义标志

21、向量 void DFS(ALGraph *G,int i) /以vi为出发点进行深度优先搜索 EdgeNode *p; printf(%4c,G-adjlisti.vertex);/访问顶点vi visitedi=1; /标记vi已访问 p=G-adjlisti.firstedge; /取vi边表的头指针 while(p)/依次搜索vi的邻接点vj，这里j=p-adjvex if (!visitedp-adjvex)/若vi尚未被访问 DFS(G,p-adjvex);/则以vj为出发点向纵深搜索 p=p-next; /找vi的下一邻接点 void DFSTraverse(ALGraph *G)

22、 /深度优先遍历以邻接表表示G int i; for(i=0;in;i+) visitedi=0; /标志向量初始化 for(i=0;in;i+) if(!visitedi) /vi未访问过 DFS(G,i); /以vi为源点开始DFS搜索 ,19,二、图的广度优先遍历 设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点，则广度优先遍历可以定义为： 1、递归定义：首先访问出发点v，接着依次访问v的所有邻接点w1，w2，wt，然后再依次访问与wl，w2，wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。 若G是连通图

23、，则遍历完成；否则，在图G中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。 说明：广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。,2、广度优先搜索的过程 在广度优先搜索过程中，设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x1，x2，xs和y1，y2，yt。 为确保先访问的顶点其邻接点亦先被访问，在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问x和y时，这两个顶点相继入队。此后，当x和y相继出队时

24、，我们分别从x和y出发搜索其邻接点x1，x2，xs和y1，y2，yt，对其中未访者进行访问并将其入队。这种方法是将每个已访问的顶点入队，故保证了每个顶点至多只有一次入队。 3、广度优先遍历的递归算法(BFS算法)邻接矩阵表示的广度优先遍历算法邻接表表示的广度优先搜索算法,21,邻接矩阵表示的广度优先遍历算法： int visitedVertexNum=0;/定义标志向量 void BFSM(MGraph *G,int k)/以vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i,j; CirQueue Q; InitQueue( /以vi为源点开始DFSM搜索 ,邻接表表示的广度优先遍

25、历算法： int visitedVertexNum=0;/定义标志向量 void BFS(ALGraph*G,int k) / 以vk为源点对用邻接表表示的图G进行广度优先搜索 int i; CirQueue Q;/须将队列定义中DataType改为int EdgeNode *p; InitQueue(/找vi的下一邻接点 /endwhile /endwhile ,5.4 生成树和最小生成树 一、生成树 自由树：无回路的连通图叫做自由树(在自由树中选定一顶点作根，则成为一棵通常的树)。 1、生成树：如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。 说明： 生成树是连通

26、图的包含图中的所有顶点的极小连通子图； 图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。2、生成树的求解方法：设图G=(V，E)是一个具有n个顶点的连通图。则从G的任一顶点(源点)出发，作一次深度(广度)优先搜索，搜索到的n个顶点和搜索过程中从一个已访问过的顶点vi搜索到一个未曾访问过的邻接点vj，所经过的边(vi，vj)(共n-1条)组成的极小连通子图就是生成树(源点是生成树的根) 。,3、深度优先生成树和广度优先生成树 由深度优先搜索得到的生成树称为深度优先生成树，简称为DFS生成树；由广度优先搜索得到的生成树称为广度优先生成树，简称为BFS生成树。 二、最小生成树 1、

27、 最小生成树：对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作： 其中：TE表示T的边集，w(u,v)表示边(u,v)的权。 权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。2、生成树和最小生成树的应用 生成树和最小生成树有许多重要的应用。,生成树和最小生成树的应用 例 网络G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。,23,23,3、普里姆(Prim)算法

28、假设G=(V,E)是连通图，最小生成树为T=(V,TE)，求T的步骤如下： 初始化：U=u0,TE=, u0是图G中任意一个顶点； 在所有uU,vV-U中，找一条权值最小的边(u,v),令TE+(u,v)=TE,U+v=U； 如果U=V,则算法结束，否则重复步骤。 4、普里姆算法的执行过程 以图G11为例说明使用普里姆算法求最小生成树T的执行过程。 说明：执行过程中红色表示已加入树T中，紫色的边表示U中的结点与V-U中的结点形成的边，兰色的结点表示V-U中的结点。,5、克鲁斯卡尔(Kruskal)算法 假设G=(V,E)是连通图，最小生成树为T=(V,TE)，求T的步骤如下：T的初始状态是只有

29、n个顶点而无边的非连通图T=(V,)。 按边长递增的顺序选择E中的边(u,v)加入到T中，要求u、v分属于T的两个连通分量；若u、v是T的当前同一个连通分量中的顶点，则舍去此边。 重复步骤直到T中所有顶点都在同一连通分量上为止。 6、克鲁斯卡尔算法的执行过程 以图G11为例说明使用克鲁斯卡尔算法求最小生成树T的执行过程。 7、两种算法的比较 普里姆算法的时间复杂度为O(n2)，与图中边数无关，该算法适合于稠密图。克鲁斯卡尔算法的时间复杂度为O(elge)， 取决于图的边数e，它较适合于稀疏图。,5.5 最短路径 一、带权图的最短路径问题 1、带权图的最短路径问题：求两个顶点间长度最短的路径。路

30、径长度是指路径上各边的权值总和。 2、源点和终点：习惯上称路径的开始顶点为源点(Source)，路径的最后一个顶点为终点(Destination)。 为了讨论方便，设顶点集V=0，1，n-1，并假定所有边上的权值均是表示长度的非负实数。 二、最短路径问题 1、单源最短路径问题：已知有向带权图(简称有向网) G=(V，E)，找出从某个源点sV到V中其余各顶点的最短路径。后3个问题可由此问题解决。 2、单目标最短路径问题：找出图中每一顶点v到某指定顶点u的最短路径。 3、单顶点对间最短路径问题：对图中某对顶点u和v，找出从u到v的一条最短路径。 4、所有顶点对间最短路径问题：对图中每对顶点u和v，

31、找出从u到v的一条最短路径。,带权图的最短路径问题 例 交通网络中常常提出的如下问题就是带权图中求最短路径的问题。 （1）两地之间是否有路相通? （2）在有多条通路的情况下，哪一条最短?其中:交通网络可以用带权图表示：图中顶点表示城镇，边表示两个城镇之间的道路，边上的权值可表示两城镇间的距离、交通费用或途中所需的时间等等。 由于交通网络存在有向性，所以一般以有向网络表示交通网络。,三、迪杰斯特拉(Dijkstra)算法求单源最短路径 由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法。1、例子： 2、按路径长度递增序产生各顶点最短路径：当前正在生成的最短路径上除终点以外，其余

32、顶点的最短路径均已生成(将源点到其自身的路径看作0)。 3、算法的基本思想： 将顶点集V分成 S(开始只包含源点s, S包含的点都是已经计算出最短路径的点) 和 V-S 集合(V-S 包含那些未确定最短路径的点)；从V-S中选取这样一个顶点w: 满足经过S集合中任意顶点 v到w的路径最短, 即满足v到w的路径最小的那个w。 其中v 属于S, w属于V-S。将w 加入S, 并从V-S中移除w；如此反复，直到V-S变空集为止。,4、说明： 开始 S中只有源点s, 从V-S中选取离s最近的点w, 则s直接到w的路径一定最短，将w加入S，并从V-S中移除w；s直接到w的路径一定最短是因为如果存在另一个

33、点w2, 使得 s-w2-w 的路径比s 直接到w短，那么w2就是我们要选取的w。 设经过算法的一些步骤后S中已有顶点v1,v2,.,vk，V-S中剩下顶点w1,w2,.,wn-k。下面选取V-S中离S集合最近的顶点w，用Dx表示从源点到x的最短路径长，则w必然满足 Dw=MinDv+Dv to w，将w加入 S集合。这个w 此时一定取得了最短路径Dw, 因为如果有其他的路径，假设是 S集合某路径-wi-w, 那么就应当去选取wi做为该点而不是w。因为 S集合某路径长Dv + Dv to wi Dv+Dv to w 与w满足的公式矛盾。,5、用迪杰斯特拉算法求单源最短路径的过程 以图G12为例说明求解过程： 设源点为顶点0，则S=0,V-S=1,2,3,4； 从S中的顶点0到V-S的顶点1,2,3,4的带 权边(10), (30),(100)中取离 0最近的点1,将1加入S，并从V-S中移除1, 则S=0,1(10),V-