第七章图.ppt

第七章 图,多对多的关系,学习要点：,图的基本概念与相关有向图、无向图、网和连通图概念。 图的邻接矩阵与邻接表存储结构及其特性。 图的深度优先和广度优先遍历方法及其在邻接表存储结构中的实现算法。 图与树的联系与区别，图的生成树与最小生成树。 图的最短路径。 图的应用：最短路径、拓扑排序与关键路径。,2,§7.1 基本概念与相关描述,7.1.1 图的基本概念 “图”（Graph）也称为网状结构，它由一个非空的顶点（vertex）集合V和一个描述顶点之间邻接关系的边（edge）集合E组成，而E中每条边连接的两个顶点都属于集合V。一个图G可以记为：G =（V，E）。 多对多的关系，非线性结构 V(G)：顶点的非空有限集合 E(G)：图中边的有限集合,3,7.1.1 图的基本概念2,有向图：弧（有向边）， :xy,x邻接到y，y邻接自x 与x、y相关联 ,4,无向图：边（无向边）， (x,y):xy,x与y相邻接 (x,y) 与x、y相关联 (x,y) = (y,x),7.1.1 图的基本概念3,子图：V(B)属于V(A)，且E(B)属于E(A)，则B是A的子图。 （B是A中的一部分）,5,7.1.2 图的相关概念,1.顶点邻接与顶点的度 顶点的度 相邻接顶点的个数，顶点vi的度记为D(vi)。 有向图顶点的度 出度：以顶点vi为弧尾的弧的个数，记为OD(vi)； 入度：以顶点vi为弧头的弧的个数，记为ID(vi)。 D(vi)=ID(vi)+OD(vi) 边数与顶点度关系 在图的顶点数n、边数e以及各顶点的度D(vi)（1in）三者之间存在如下关系：,6,2e= D(vi),7.1.2 图的相关概念2,1.路径与路径长度,7, 无向图的路径 在顶点vi与顶点vj之间存在一个边的序列：（vi, vi1），（vi1, vi2），（vim, vj）。 有向图的路径 顶点vi与顶点vj之间存在一个弧的序列：， 。 路径长度 由顶点vi到顶点vj路径上拥有的边的个数。 简单路径与回路 若在一条路径上出现的顶点都不同，则称其为“简单路径”或“简单回路（环cycle）”。,7.1.2 图的相关概念3,3.无向完全图与有向完全图 有向完全图：每个顶点都与其它任意顶点有弧。 共 条边。,n*(n-1),n*(n-1)/2,8,无向完全图：每个顶点都与其它任意顶点有边。 共 条边。,7.1.2 图的相关概念4,4.连通图与连通分量, 连通分量 在无向图G中，尽可能多地从集合V及E里收集顶点和边，使它们成为该图的一个极大的连通子图，这个子图就被称为是无向图G的一个“连通分量”。,9, 连通图 在无向图G中，任意一对顶点之间都是连通的。,7.1.2 图的相关概念4,4.连通图与连通分量2,10, 强连通图和弱连通图 在有向图G中，若对其中任意两个顶点vi和vj互有路径可达，则称G强连通图；如果任意两个顶点都至少存在单向路径，则称G是弱连通图。 n个顶点的强连通图应当至少有n条弧。 强连通分量和弱连通分量 有向图G中的极大强连通子图称为G的强连通分量，而其中的极大弱连通子图称为G的弱连通分量。,7.1.2 图的相关概念5,5.边的权值与网络,11, 边的权值 图的边或弧依附上的某种数值称为“权值”或“权（weight）”。例如地图上连接两个城市的铁路线在其上附有该铁路线的里程数等。 网络 边或弧上带有权的图称为“网络”或“网图”。,§7.2 图的存储,7.2.1基于邻接矩阵存储 用二维数组表示顶点的邻接关系 1、图的邻接矩阵（n顶点用n阶方阵）,12,A =,1、图的邻接矩阵2,邻接矩阵特点： 无向图邻接矩阵对称，有向图不对称 无向图第i行(列)非零元素个数即为结点i的度 有向图第i行(列)非零元素个数即为结点i的出(入)度 容易确认任两点之间是否有边，但扫描边数代价大 （对每个结点进行检测）,13,2、网络的邻接矩阵,14,3、邻接矩阵存储算法,算法7-1 有向图G邻接矩阵算法。 设置一个一维数组Gv，用于存放G的顶点数据信息；设置一个二维数组Ge，用于存放G中有关弧的信息；设置变量n和e，记录图的顶点个数和弧的个数信息。,15,00 Create_Gm(MGraph *Gm) 01 02 scanf(“%d%d“, 15 16 ,7.2.2 基于邻接表存储,00 struct enode /* 定义边结点结构 */ 01 02 int adjvex; 03 struct enode *next; 04 ;,16,05 struct vnode /* 定义顶点结点结构 */ 06 07 vertextype vertex; /* 顶点类型为vertextype */ 08 struct enode *fadj; 09 ;,10 typedef struct /* 定义一个图邻接表类型 */ 11 12 truct vnode GvMAX; /* 图的邻接表 */ 13 int n, e; /* 图的顶点数、边数信息 */ 14 RGraph;,7.2.2 基于邻接表存储2,17,图7-12 图7-5（5）所示无向图邻接表存储结构,7.2.2 基于邻接表存储3,网络的邻接表：,18,7.2.2 基于邻接表存储4,算法7-2 有向图邻接表存储算法。 设置由单链表表头结点组成的一维数组Gv，用于存放图的顶点序号（vertex）以及指向顶点单链表的指针（fadj），类型为Gnode；设置变量n和e，记录图的顶点个数和弧的个数信息。,19,00 Create_Gr(RGraph *Gr) 01 02 Gnode *ptr; 03 scanf(“%d%d“, 16 17 ,问题：如何求有向图顶点的入度？,解：可建立有向图的逆邻接表,20, 正邻接表：方便求顶点的出度 逆邻接表：方便求顶点的入度,§7.3 图的遍历,从图的某一个顶点出发访问图中的所有顶点，且每个顶点只被访问一次的过程。,21,步骤如下： 在图G中指定一个顶点v0作为遍历开始顶点，先访问v0并将其进行适当标记表明已被访问。 依次从v0的还未被访问的各个邻接顶点w出发递归地进行深度优先搜索。 如果图中还存在未访问过的顶点，则选其中之一由其出发重复上述步骤“”“”，直到图中所有顶点都被访问。,7.3.1 深度优先遍历,过程（利用栈结构）：, 指定起点q 访问q q进栈 栈空否？ a：不空，转 b：空，转, 找栈顶元素未访问邻接点q a：找到，转 b：找不到，出栈，转 结束,遍历结果：n结点，（n1）条边，无回路 按遍历过程经过的边为一棵深度优先生成树。,22,例子：,求下图从顶点v0出发的深度遍历序列。,23,解： v0 v1 v3 v4 v5 v2,算法7-3 基于邻接表的无向图深度优先搜索算法,00 Depth_Gr(RGraph *Gr, int n) 01 02 for (i=1; i=n; i+) /* 记录顶点是否被访问的一维数组flag初始化 */ 03 flagi = 0; 04 for (i=1; i=n; i+) /* 对整个图进行深度优先搜索遍历 */ 05 06 if (flagi = 0) 07 DFS(Gr, i, flag); /* 从顶点vi开始对图进行深度优先遍历 */ 08 09 ,24,算法7-3 基于邻接表的无向图深度优先搜索算法2,10 DFS(RGraph *Gr, int i, int flag) 11 12 flagi =1; /* 将顶点vi设置为已访问过标志 */ 13 printf (“%d“, i); 14 for (ptr = Gvi.fadj; ptr != NULL; ptr = ptr-next) /* 沿着vi的链表前进 */ 15 16 k = ptr-adjvex; 17 if (flagk = 0) /* 对未访问的顶点继续深度优先搜索 */ 18 DFS(Gr, k, flag); 19 20 ,25,上机：,使用邻接表存储图，编写其深度优先遍历的非递归算法。,26,过程： 访问地点；起点进栈； while （栈不空） 找栈顶未访问邻接点p； if 找到 访问；进栈； else 出栈； ,7.3.2 广度优先遍历,步骤如下： 在图中指定一个顶点v0为遍历起始点，访问顶点v0并将其进行标记以表明被访问； 依次访问 v0 的所有相邻顶点 w1, w2, , wx ，此时需要为 v 的邻接顶点规定一种顺序，然后依次访问与 w1, w2, , wx 邻接的所有未访问顶点直到所有已访问顶点的相邻顶点都已访问。 如果图中还有未访问顶点，则选择其中之一作为新的遍历起始顶点，由其出发进行广度优先搜索直到所有顶点都已访问。,27,算法7-4 基于邻接表的无向图广度优先搜索算法,00 Breadth_Gr(RGraph *Gr, int n) 01 02 for (i=0; in; i+) /* 记录顶点是否被访问的一维数组flag初始化 */ 03 flagi = 0; 04 for (i=0; in; i+) /* 对整个图进行广度优先搜索遍历 */ 05 if (flagi = 0) 06 BFS(Gr, i, flag); /* 从顶点vi开始对图进行广度优先遍历 */ 07 ,28,算法7-4 基于邻接表的无向图广度优先搜索算法2,08 BFS(RGraph *Gr, int i, int flag ) 09 10 Qs_front=0; /* 队首、队尾指针初始化 */ 11 Qs_rear=0; 12 Qs_rear + ; 13 QsQs_rear = i ; /* 让顶点vi的序号进队列 */ 14 flagi = 1; 15 printf (“%d“, i); /* 访问顶点vi */ 16 while (front rear) 17 18 Qs_front+ ; /* 队首元素出队 */ 19 i = QsQs_front ; 20 ptr = Gvi.fadj; /* 得到该顶点链表首元素，由ptr指向 */,29,算法7-4 基于邻接表的无向图广度优先搜索算法3,21 while (ptr != NULL) 22 23 k = ptr-adjvex; 24 if (flagk = 0) 25 26 flagk = 1; 27 pringf (“%d“, k); 28 Qs_rear + ; 29 QsQs_rear = k ; 30 31 ptr = ptr-next; 32 33 34 ,30,过程（利用队列结构）：, 访问指定起点q q所有未访问邻接点依次访问、入队列 队列空否： a：不空，出队列赋为q，转 b：空，转 结束,遍历结果：n结点，（n1）条边，无回路 按遍历过程经过的边为一棵广度优先生成树。,31,例子：,求下图从顶点v0出发的广度遍历序列。,32,解： v0 v1 v2 v3 v4 v5,注意：,深度优先遍历或者广度优先遍历能遍历到指定起点所在的连通分量中的所有顶点。,33,7.3.3简单路径与路径长度最小路径,给定一个图G和其中两个顶点vi和vj，通常存在着vi和vj连接多条简单路径，其中必有一条路径长度最短的路径。 具体做法如下：,34,1) 将链队列结点改为“双链”结点 即结点中包含next 和prior两个指针； 2) 修改进入队列操作 插入新的队尾结点时，令其prior域的指针指向刚刚出队列的结点，即当前的队头指针所指结点； 3) 修改出队列的操作 出队列时，仅移动队头指针，而不将队头结点从链表中删除。,例子：,设有如图所示无向图，需要计算出从v0到v5的路径长度最短的路径。,35,解：链队列结构：,例子（续）：,计算过程：,36,§7.4 生成树与最小生成树,7.4.1 图的生成树 生成树极小连通子图（n-1）条边 “极小”的含义包括两个方面含义： 如果在生成树中去掉任何一条边，生成树将会不再连通； 如果在生成树中添加任何一条边，生成树将会出现回路。,37,7.4.1 图的生成树2,1、深度和广度优先生成树 从连通图G任一顶点出发对G进行遍历可访问G的所有顶点。遍历时经过的边加上所有顶点就构成G的一个连通子图，这样的连通子图就是G的一棵生成树。 生成树不唯一：深度优先生成树（DFS） 广度优先生成树（BFS） ,38,例子：,设有如图所示无向图，画出其深度优先和广度优先生成树。,39,解：,例子：,设有如图所示有向图，画出其深度优先和广度优先生成树。,40,解：,7.4.2 最小生成树,1、图的最小生成树 网络中所有生成树中代价最小的树。 复习：网络的邻接矩阵：,41,7.4.2 最小生成树2,2、普里姆(Prim)算法 原理：选取一个顶点作为起点，每次通过代价最小的边选择一个顶点并入生成树中，直到包含所有顶点。 建立无向网络并基于prim算法求最小生成树算法详见7.4.2节算法7-6。 基本思想： 将把图G中的顶点分成两部分：已在MST中的顶点集合U，还未在MST的顶点集合VU。 在VU里挑选出与U中某个顶点相距最近（即权值最小）的那个顶点，把这个顶点从VU移到U中。由此使得集合U不断扩大，VU不断缩小，当U=V，VU=时，算法结束。,42,练习：,用普里姆算法（Prim）的思想，画出该图生成最小生成树的过程。,43,适合：与顶点数有关，适合边稠密的网络。 总的时间复杂度：O(n2),7.4.2 最小生成树3,3、克鲁斯卡尔(Kruskal)算法 原理：所有边按权排序，每次取最短边，如不构成回路，则并入生成树中，否则舍弃。直到并入了（n-1）条边。 建立无向网络并基于Kruscal算法求最小生成树算法详见7.4.2节算法7-7。 具体步骤： 以图G的E为基础，按照各边的权值，由小到大对它们进行挑选； 如果挑选出来的边的两个顶点分属S中的两个不同的连通分量，那么就将此边从E中去除，并用此边将S中的那两个连通分量连接成一个连通分量，成为最小生成树S中的一个新连通分量； 如果挑选出来的边的两个顶点属于S中的同一个连通分量，那么就将其从E中舍弃，重新再挑选； 不断地实行（1）（3）步，当S里只剩下一个连通分量时，算法终止。,44,练习：,用克鲁斯卡尔算法（Kruskal）的思想，画出该图生成最小生成树的过程。,45,总的时间复杂度：与边排序算法有关 适合：与边有关，适合边稀疏的网络。,3、克鲁斯卡尔(Kruskal)算法2,问题：如何判断是否构成回路？ 定义连通分量数组ringn，初始时各个ringi各不相同，找到边（i，j）时，判断ringi与ringj是否相等： 相等：说明i，j在同一个连通分量，舍弃； 不相等： i，j在不同连通分量，边（i，j）并入生成树中，并把所有与ringi相等的ring值改为ringj。,46,§7.5 最短路径,问题的提出： A、B有若干路径相通，如何找寻一代价最小的路径？ 例子：,47,§7.5 最短路径2,1、单源最短路径,48,Dijkstra算法具体步骤： 初始时，集合U里只含一个源点u，集合VU里是图中除u以外的所有顶点，u到其它顶点的距离是它们间弧的权值； 从VU里挑选出一个与源点u的距离为最小的顶点v，把它从VU移到U里，然后对VU里剩下的顶点（比如k）到源点u的距离进行修改，方法是若图中存在弧（v, k），且该弧的权值加上u到v的距离之和小于原先u到k的距离时，就用此“和”取代原先u到k的距离，否则原先u到k的距离保持不变； 逐次对集合VU实行操作（2），当VU为空时，算法结束，所求得的u到各顶点的距离即是源点到其它顶点的最短路径长度。 求单源最短路径的Dijkstra算法详见7.5节算法7-8。,例子：,利用Dijkstra算法，求下图源点v1到其它顶点的最短路径。,49,例子（续）：,基于Dijkstra算法最短路径计算过程：,50,§7.5 最短路径3,2、顶点对间最短路径,51,已知有向网图G=（V，E），求其中任意一对顶点之间的最短路径。 Floyd算法具体步骤： 初始时，把邻接矩阵记为D(0)，它的元素记录了图中各弧的权值； 逐次把顶点vk(1kn)插入到矩阵所有元素中去进行探测，如果矩阵原先有路径（vi, vj）(i j)，现在插入vk后，有路径（vi, vk）和（vk, vj），且： D (vi, vk) + D (vk, vj) D (vi, vj) 那么，就用D (vi, vk) + D (vk, vj)代替D (vi, vj)，于是形成一个新的矩阵D(k)； 在完成n次探测后，矩阵D(n)里记录了各顶点对之间的最短路径。,例子：,利用Floyd算法，求下图中各顶点对的最短路径长度。,52,例子（续）：,基于Floyd算法最短路径计算过程：,53,§7.6 有向无环网及应用,（有起点，终点，不能包含回路） 7.6.1 拓扑排序,54,例子： 计算机专业课程设置关系：,§7.6 有向无环网及应用,7.6.1 拓扑排序2,55,例子（续）：课程先修关系图：,学习顺序：C1 C2C3C5C4C6C8C9C7C10 或者：C1 C8C9C2C5C3C4C10C7C6,§7.6 有向无环网及应用,7.6.1 拓扑排序3 AOV网 有向图G中，以顶点表示活动，弧表示各活动之间的先后关系的网络简称“AOV网”。 前驱 直接前驱 后继 直接后继 拓扑排序 将AOV网中所有顶点基于前驱与后继关系排成一个线性序列的过程就称为“拓扑排序”，所得到的序列就是一个顶点的“拓扑序列”。,56,§7.6 有向无环网及应用,7.6.1 拓扑排序4 拓扑排序基本步骤如下： 在AOV网里选择一个没有前驱（即入度为0）的顶点，并加以输出； 接着删除该顶点以及以它为尾的所有弧； 重复执行、步，直到网中不再有入度为0的顶点时止。 （结果不唯一） 结果：如网中全部顶点都被输出，表明拓扑排序成功；否则表示网中存有环，此时AOV网是一个DAG网，无法完成拓扑排序。,57,算法7-9 对AOV网进行拓扑排序的算法,00 void TopologicalSort(VNnode adj,int n) 01 02 int i,j; 03 int Stmaxv,top=-1; /* 栈St指针为top */ 04 for (i=0,in;i+) 05 if (adji.count=0) /* 入度为0的顶点进栈 */ 06 top+; 07 Sttop=I; 08 ,58,算法7-9 对AOV网进行拓扑排序的算法2,09 while (top-1) /* 栈非空是进行循环 */ 10 11 i=Sttop;top; /* 出栈 */ 12 printf(“%d ”,i); /* 输出顶点 */ 13 p=adji.firstarc; /* 找出第一个相邻顶点 */ 14 while(p!=null) 15 16 j=p-adjvex; 17 adji.count-; 18 if(adjj.count=0) /* 入度为0相邻顶点入栈 */ 19 20 top+; 21 Sttop=j; 22 23 p=p-nextarc; /* 找出下一个相邻顶点 */ 24 25 26 ,59,例子：,对下图（a）所示的AOV网进行拓扑排序以获得它的拓扑序列。,60,拓扑序列1： v2 v5 v1 v4 v3 v7 v6 拓扑序列2 ： v1 v3 v2 v5 v4 v6 v7 ,7.6.2 关键路径,AOE网 若在有向无环网络中，以顶点表示事件（或活动进行过程中的某个点），以有向边表示活动，边上的权代表完成活动所需要的代价，则G就称为“AOE网”。 问题例子：完成下图V1到V10整个工期至少需要多少时间？,61,7.6.2 关键路径2,1、关键路径与关键活动 关键路径：从起点到终点的路径中代价最大的。 （不唯一） 关键活动：关键路径上的活动 缩短工期的关键：加快关键活动的进度。 （注意要受到其他关键活动的制约）,62,7.6.2 关键路径2,1、关键路径与关键活动2 问题：如何寻找关键活动，从而确定关键路径呢？ 首先学习定义的几个变量： vei代表顶点vi发生的最早时间，是从起点v1到vi的最大路径长度。 ei代表活动ai发生的最早时间。因为事件vi的发生代表了以vi为起点的各项活动均可开始，所以事件vi发生的最早时间也是所有以vi为起点的活动的最早发生时间，即ei= vei。 vli代表在不推迟整个工程最小工期的情况下，顶点vi发生的最迟时间，是完成终点顶点vn的最早时间ven减去vi到vn的最大路径长度。 li代表活动ai发生的最迟时间。,63,7.6.2 关键路径2,1、关键路径与关键活动3 寻找关键活动步骤如下： （1）求vei。 从开始顶点v1开始，令ve1=0，按事件发生的先后次序求各个顶点的最早发生时间vei。,64,其中T表示以vi为终点的所有弧的起点的集合；dut()表示弧的权值。,7.6.2 关键路径2,1、关键路径与关键活动3 寻找关键活动步骤如下： （2）求vli。 从结束顶点vn开始，令vln=ven，也就是整个工程的最大路径长度，按事件发生的先后次序的逆序求各个顶点的最迟发生时间vli。,65,其中S表示以vi为起点的所有弧的终点的集合。,7.6.2 关键路径2,1、关键路径与关键活动3 寻找关键活动步骤如下： （3）求vli。 各活动的最早发生时间为活动起点顶点的最早发生时间。如活动ai代表的弧为，则ei= vei。 （4）求li。 各活动的最迟发生时间为活动终点顶点的最迟发生时间减去活动的权值。如活动ai代表的弧为，则li= vlj- dut()。,66,例子：,以下图AOE网为例，求关键活动和关键路径。,67,例子（续）：,首先，求各事件和活动的最早、最迟发生时间：,68,例子（续）：,然后，根据活动的最早、最迟发生时间确定关键活动：,69,由右表可知，a1，a3，a4，a6，a7，a9，a10，a11，a12为关键活动。,例子（续）：,最后，根据关键活动得到关键路径：,70,a1，a3，a4，a6，a7，a9，a10，a11，a12为关键活动。,7.6.2 关键路径2,2、关键路径算法 步骤如下： （1）采用邻接表存储AOE网，对邻接表做稍微的改良，邻接表的顶点结点需要保存对应顶点的入度信息。 （2）进行拓扑排序，保存拓扑排序序列。 （3）生成各顶点的最早发生时间。 （4）生成各顶点的最迟发生时间。 （5）生成关键路径。对比顶点的最早发生时间与最迟发生时间，如果相一致的则是关键路径上的顶点，形成关键路径。 求AOE网的关键路径算法详见7.6.2节算法7-10 。,71,本章小结,本章基本内容,