图论基础知识.ppt

图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 二、无向二、无向图图的的传递闭传递闭包包问题问题 三、生成三、生成树树与最小生成与最小生成树问题树问题 四、最短路径四、最短路径问题问题 五、拓扑排序与关五、拓扑排序与关键键路径路径 六、六、图论图论模型的建立模型的建立 七、匹配七、匹配 八、最大流八、最大流1.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 1 1、回、回顾顾三种数据三种数据结结构模型：构模型：线线性表、性表、树树、图图 2 2、图图的基本概念：的基本概念：图图=（顶顶点点集集，边边集集），顶顶点点集集必必须须非非空空，什什么么是是顶顶点点，什什么么是是边边？图图的分的分类类：无向：无向图图、有向、有向图图，主要看是否可逆，主要看是否可逆 带权图带权图：权权的含的含义义，不加，不加权权的的图图也可以也可以认为认为所有所有边边上的上的权权都是都是1 1。阶阶和度：一个和度：一个图图的的阶阶是指是指图图中中顶顶点的个数点的个数 如果如果顶顶点点A A和和B B之之间间有一条有一条边边相相连连，则则称称A A和和B B是关是关联联的的 顶顶点的度：与点的度：与该顶该顶点相关点相关联联的的边边的数目，有奇点、偶点之分的数目，有奇点、偶点之分 对对于有向于有向图图：有入度和出度之分：有入度和出度之分2.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 2 2、图图的基本概念：的基本概念：定理：无向定理：无向图图中所有中所有顶顶点的度之和等于点的度之和等于边边数的数的2 2倍；倍；有向有向图图中所有中所有顶顶点的入度之和等于所有点的入度之和等于所有顶顶点的出度之和；点的出度之和；任意一个无向任意一个无向图图一定有偶数个（或一定有偶数个（或0 0个）奇点；个）奇点；完全完全图图：一个一个n n阶阶的完全无向的完全无向图图含有含有n*(n-1)/2n*(n-1)/2条条边边；一个一个n n阶阶的完全有向的完全有向图图含有含有n*(n-1)n*(n-1)条条边边；稠密稠密图图：当一个：当一个图图的的边边数接近完全数接近完全图时图时；稀疏稀疏图图：当一个：当一个图图的的边边数数远远远远少于完全少于完全图时图时；在具体使用在具体使用时时，要，要选选用不同的存用不同的存储结储结构；构；子子图图：从一个：从一个图图中取出若干中取出若干顶顶点、若干点、若干边边构成的一个新的构成的一个新的图图；3.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 2 2、图图的基本概念：的基本概念：路径：路径：对对于于图图G=G=（V V，E E），），对对于于顶顶点点a a、b b，如果存在一些，如果存在一些顶顶点序列点序列 x x1 1=a,x=a,x2 2,x,xk k=b(k1)=b(k1)，且（，且（x xi i,x,xi+1i+1）EE，i=1,2k-1i=1,2k-1，则则称称 顶顶点序列点序列x x1 1,x,x2 2,x,xk k为顶为顶点点a a到到顶顶点点b b的一条路径，而路径上的一条路径，而路径上边边 的数目（即的数目（即k-1k-1）称）称为该为该路径的路径的长长度。度。并称并称顶顶点集合点集合xx1 1,x,x2 2,x,xk k 为为一个一个连连通集。通集。简单简单路径：如果一条路径上的路径：如果一条路径上的顶顶点除了起点和点除了起点和终终点可以相同外，其它点可以相同外，其它 顶顶点均不相同，点均不相同，则则称此路径称此路径为为一条一条简单简单路径；起点和路径；起点和终终点点 相同的相同的简单简单路径称路径称为为回路（或回路（或环环）。）。4.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 2 2、图图的基本概念：的基本概念：路径和路径和简单简单路径的路径的举举例：例：左左图图123123是一条是一条简单简单路径，路径，长长度度为为2 2，而而1341313413就不是就不是简单简单路径；路径；右右图图121121为为一个回路。一个回路。5.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 2 2、图图的基本概念：的基本概念：连连通：通：在一个在一个图图中，如果从中，如果从顶顶点点U U到到顶顶点点V V有路径，有路径，则则称称U U和和V V是是连连通的；通的；有根有根图图：在一个在一个图图中，若存在一个中，若存在一个顶顶点点WW，它与其它，它与其它顶顶点都是点都是连连通的，通的，则则称此称此图为图为有根有根图图，顶顶点点WW即即为为它的根。它的根。上面的两个上面的两个图图都是有根都是有根图图，左，左图图的的1 1、2 2、3 3、4 4都可以作都可以作为为根；根；而右而右图图的的1 1、2 2才可以作才可以作为为根。根。6.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 2 2、图图的基本概念：的基本概念：连连通通图图：如果一个无向如果一个无向图图中，任意两个中，任意两个顶顶点之点之间间 都是都是连连通的，通的，则则称称该该无向无向图为连图为连通通图图。否。否则则称称为为非非连连通通图图；左；左图为图为一个一个连连通通图图。强强连连通通图图：在一个有向在一个有向图图中，中，对对于任意两个于任意两个顶顶点点U U和和V V，都存在着一条从，都存在着一条从U U到到V V的的有向路径，同有向路径，同时时也存在着一条从也存在着一条从V V到到U U的有向路径，的有向路径，则则称称该该有向有向图为图为强强连连通通图图；右；右图图不是一个不是一个强强连连通通图图。连连通分支：通分支：一个无向一个无向图图的的连连通分支定通分支定义为该图义为该图的最大的最大连连通子通子图图，左，左图图的的连连通分支是它本身。通分支是它本身。强强连连通分支：通分支：一个有向一个有向图图的的强强连连通分支定通分支定义为该图义为该图的最大的的最大的强强连连通子通子图图，右右图图含有两个含有两个强强连连通分支，一个是通分支，一个是1 1和和2 2构成的一个子构成的一个子图图，一个是，一个是3 3独立构独立构成的一个子成的一个子图图。7.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 3 3、图图的存的存储结储结构（构（n n阶阶e e条条边边）：）：邻邻接矩接矩阵阵 边边集数集数组组 邻邻接表接表 优优点点 直直观观方便方便,Ai,Ai，jj时间时间O O（1 1）存存储储稀疏稀疏图时图时，空，空间间效率比效率比较较好，也好，也比比较较直直观观 便于便于查查找任一找任一顶顶点的关点的关联边联边及及关关联联点点,查查找运算的找运算的时间时间复复杂杂性平均性平均为为O(e/n)O(e/n)缺点缺点 存存储储稀疏稀疏图图，会造，会造成很大的空成很大的空间间浪浪费费 不适合不适合对顶对顶点的运点的运算和算和对对任意一条任意一条边边的运算的运算 要要查查找找一一个个顶顶点点的的前前驱驱顶顶点点和和以以此此顶顶点点为为终终点点的的边边、以以及及该该顶顶点点的的入入度度就就不不方方便便了了，需需要要扫扫描描整整个个表表，时时间间复复杂杂度度为为O O（n+en+e）。可以用十字）。可以用十字邻邻接表改接表改进进适用适用场场合合 处处理理1 1个个顶顶点的度点的度和关和关联边联边，O O（n n）适合于存适合于存储储稀疏稀疏图图和那些和那些对边对边依次依次进进行行处处理的运算理的运算 对对任一任一顶顶点的关点的关联边联边（顶顶点）点）进进行不断、重复的运算行不断、重复的运算 空空间间复复杂杂度度 O O（n*nn*n）O O（3e3e）O O（6e+2n6e+2n）8.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 4 4、图图的遍的遍历历：从从图图中中某某一一顶顶点点出出发发系系统统地地访访问问图图中中所所有有顶顶点点，使使每每个个顶顶点点恰恰好好被被访访问问一一次次，这这种种运运算算操操作作被被称称为为图图的的遍遍历历。为为了了避避免免重重复复访访问问某某个个顶顶点点，可可以以设设一一个个标标志志数数组组visitedivisitedi，未未访访问问时时值值为为falsefalse，访访问问一一次次后就改后就改为为truetrue。图图的遍的遍历历分分为为深度深度优优先遍先遍历历和广度（和广度（宽宽度）度）优优先遍先遍历历两种方法。两种方法。图图的深度的深度优优先遍先遍历历：类类似于似于树树的先序遍的先序遍历历。从。从图图中某个中某个顶顶点点V Vi i出出发发，访问访问此此顶顶点并作已点并作已访问标记访问标记，然后从，然后从V Vi i的一个未被的一个未被访问过访问过的的邻邻接点接点V Vj j出出发发再再进进行深度行深度优优先遍先遍历历，当，当V Vi i的所有的所有邻邻接点都被接点都被访问过时访问过时，则则退回到上退回到上一个一个顶顶点点V Vk k，再从，再从V Vk k的另一个未被的另一个未被访问过访问过的的邻邻接点出接点出发进发进行深度行深度优优先遍先遍历历，直至，直至图图中所有中所有顶顶点都被点都被访问访问到到为为止。止。9.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 4 4、图图的遍的遍历历：左左图图从从顶顶点点a a出出发发，进进行深度行深度优优先遍先遍历历的的结结果果为为：a a，b b，c c，d d，e e，g g，f f右右图图从从V V1 1出出发进发进行深度行深度优优先遍先遍历历的的结结果果为为：V V1 1，V V2 2，V V4 4，V V8 8，V V5 5，V V3 3，V V6 6，V V7 7对对下面两个下面两个图图分分别进别进行深度行深度优优先遍先遍历历，写出遍，写出遍历结历结果。果。注意：分注意：分别别从从a和和V1出出发发。10.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 4 4、图图的遍的遍历历：对对于一个于一个连连通通图图，深度，深度优优先遍先遍历历的的递归过递归过程如下：程如下：Procedure dfs(i:integer)Procedure dfs(iinteger)；图图用用邻邻接矩接矩阵阵存存储储 BeginBegin 访问顶访问顶点点i i；Visitedi:=TrueVisitedi:=True；For j:=1 to n do For j:=1 to n do 按深度按深度优优先搜索的先搜索的顺顺序遍序遍历历与与i i相关相关联联的所有的所有顶顶点点 BeginBegin If(Not Visitedj)and(ai,j=1)Then dfs(j)If(Not Visitedj)and(ai,j=1)Then dfs(j)；End End；EndEnd；以上以上dfs(i)dfs(i)的的时间时间复复杂杂度度为为O O（n*nnn）。）。对对于一个非于一个非连连通通图图，调调用一次用一次dfs(i)dfs(i)，即按深度，即按深度优优先先顺顺序依次序依次访问访问了了顶顶点点i i所在的（所在的（强强）连连通分支，所以通分支，所以只要在主程序中加上：只要在主程序中加上：for i:=1 to n do for i:=1 to n do 深度深度优优先搜索每一个未被先搜索每一个未被访问过访问过的的顶顶点点 if not Visited if not Visited（I)then dfs(i);I)then dfs(i);11.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 4 4、图图的遍的遍历历：图图的的宽宽（广）度（广）度优优先遍先遍历历：类类似于似于树树的按的按层层次遍次遍历历。从。从图图中某个中某个顶顶点点V V0 0出出发发，访问访问此此顶顶点，然后依次点，然后依次访问访问与与V V0 0邻邻接的、未被接的、未被访问过访问过的所有的所有顶顶点，然点，然后再分后再分别别从从这这些些顶顶点出点出发进发进行广度行广度优优先遍先遍历历，直到，直到图图中所有被中所有被访问过访问过的的顶顶点的相点的相邻顶邻顶点都被点都被访问访问到。若此到。若此时图时图中中还还有有顶顶点尚未被点尚未被访问访问，则则另另选图选图中中一个未被一个未被访问过访问过的的顶顶点作点作为为起点，重复上述起点，重复上述过过程直到程，直到图图中所有中所有顶顶点都被点都被访问访问到到为为止。止。对对上面两个上面两个图图分分别别从从a和和V1出出发进发进行行宽宽度度优优先遍先遍历历，写出遍，写出遍历结历结果。果。12.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 4 4、图图的遍的遍历历：对对上面两个上面两个图图分分别别从从a和和V1出出发进发进行行宽宽度度优优先遍先遍历历，写出遍，写出遍历结历结果。果。a a，b b，d d，e e，f f，c c，g g V V1 1，V V2 2，V V3 3，V V4 4，V V5 5，V V6 6，V V7 7，V V8 8 13.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 4 4、图图的遍的遍历历：深度深度优优先遍先遍历历与与宽宽度度优优先遍先遍历历的比的比较较：深度深度优优先遍先遍历实际历实际上是尽可能地走上是尽可能地走“顶顶点表点表”；而广度而广度优优先遍先遍历历是尽可能沿是尽可能沿顶顶点的点的“边边表表”进进行行访问访问，然后再沿然后再沿边边表表对应顶对应顶点的点的边边表表进进行行访问访问，因此，有关，因此，有关边边表表的的顶顶点需要保存点需要保存(用用队队列，先列，先进进先出先出)，以便，以便进进一步一步进进行广度行广度优优先遍先遍历历。下面是广度下面是广度优优先遍先遍历历的的过过程：程：14.图论图论算法与算法与实现实现 一、一、图论图论基基础础知知识识 4 4、图图的遍的遍历历：时间时间：O（n*n）Procedure bfs(i:integer)；宽宽度度优优先遍先遍历历，图图用用邻邻接矩接矩阵阵表示表示Begin 访问顶访问顶点点i；Visitedi:=true;顶顶点点i入入队队q；while 队队列列q非空非空 do begin 从从队队列列q中取出中取出队队首元素首元素v；for j:=1 to n do begin if(not Visitedj)and(av,j=1)then begin 访问顶访问顶点点j；Visitedj:=true;顶顶点点j入入队队q end;end;end;End；15.