图论基础知识

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图论算法与实现,一、图论基础知识,二、无向图的传递闭包问题,三、生成树与最小生成树问题,四、最短路径问题,五、拓扑排序与关键路径,六、图论模型的建立,七、匹配,八、最大流,常州市第一中学 林厚从,图论算法与实现,一、图论基础知识,1、回顾三种数据结构模型：线性表、树、图,2、图的基本概念：,图=（顶点集，边集），顶点集必须非空，什么是顶点，什么是边？,图的分类：无向图、有向图，主要看是否可逆,带权图：权的含义，不加权的图也可以认为所有边上的权都是1。,阶和度：一个图的阶是指图中顶点的个数,如果顶点,A,和,B,之间有一条边相连，则称,A,和,B,是关联的,顶点的度：与该顶点相关联的边的数目，有奇点、偶点之分,对于有向图：有入度和出度之分,常州市第一中学 林厚从,图论算法与实现,一、图论基础知识,2、图的基本概念：,定理：无向图中所有顶点的度之和等于边数的2倍；,有向图中所有顶点的入度之和等于所有顶点的出度之和；,任意一个无向图一定有偶数个（或0个）奇点；,完全图：,一个,n,阶的完全无向图含有,n*(n-1)/2,条边；,一个,n,阶的完全有向图含有,n*(n-1),条边；,稠密图：当一个图的边数接近完全图时；,稀疏图：当一个图的边数远远少于完全图时；,在具体使用时，要选用不同的存储结构；,子图：从一个图中取出若干顶点、若干边构成的一个新的图；,常州市第一中学 林厚从,图论算法与实现,一、图论基础知识,2、图的基本概念：,路径：对于图,G=（V，E），,对于顶点,a、b，,如果存在一些顶点序列,x,1,=a,x,2,x,k,=b(k1)，,且（,x,i,x,i,+1,）E，i=1,2k-1，,则称,顶点序列,x,1,x,2,x,k,为顶点,a,到顶点,b,的一条路径，而路径上边,的数目（即,k-1）,称为该路径的长度。,并称顶点集合,x,1,x,2,x,k,为一个连通集。,简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它,顶点均不相同，则称此路径为一条简单路径；起点和终点,相同的简单路径称为回路（或环）。,常州市第一中学 林厚从,图论算法与实现,一、图论基础知识,2、图的基本概念：,路径和简单路径的举例：,左图123是一条简单路径，长度为2，,而13413就不是简单路径；,右图121为一个回路。,常州市第一中学 林厚从,图论算法与实现,一、图论基础知识,2、图的基本概念：,连通：,在一个图中，如果从顶点,U,到顶点,V,有路径，则称,U,和,V,是连通的；,有根图：,在一个图中，若存在一个顶点,W，,它与其它顶点都是连通的，则称此图为有根图，顶点,W,即为它的根。,上面的两个图都是有根图，左图的1、2、3、4都可以作为根；,而右图的1、2才可以作为根。,常州市第一中学 林厚从,图论算法与实现,一、图论基础知识,2、图的基本概念：,连通图：,如果一个无向图中，任意两个顶点之间 都是连通的，则称该无向图为连通图。否则称为非连通图；左图为一个连通图。,强连通图：,在一个有向图中，对于任意两个顶点,U,和,V，,都存在着一条从,U,到,V,的有向路径，同时也存在着一条从,V,到,U,的有向路径，则称该有向图为强连通图；右图不是一个强连通图。,连通分支：,一个无向图的连通分支定义为该图的最大连通子图，左图的连通分支是它本身。,强连通分支：,一个有向图的强连通分支定义为该图的最大的强连通子图，右图含有两个强连通分支，一个是1和2构成的一个子图，一个是3独立构成的一个子图。,常州市第一中学 林厚从,图论算法与实现,一、图论基础知识,3、图的存储结构（,n,阶,e,条边）：,邻接矩阵,边集数组,邻接表,优点,直观方便,Ai，j,时间,O（1）,存储稀疏图时，空间效率比较好，也比较直观,便于查找任一顶点的关联边及关联点,查找运算的时间复杂性平均为,O(e/n),缺点,存储稀疏图，会造成很大的空间浪费,不适合对顶点的运算和对任意一条边的运算,要查找一个顶点的前驱顶点和以此顶点为终点的边、以及该顶点的入度就不方便了，需要扫描整个表，时间复杂度为,O（n+e）。,可以用十字邻接表改进,适用,场合,处理1个顶点的度和关联边，,O（n）,适合于存储稀疏图和那些对边依次进行处理的运算,对任一顶点的关联边（顶点）进行不断、重复的运算,空间,复杂度,O（n*n）,O（3e）,O（6e+2n）,常州市第一中学 林厚从,图论算法与实现,一、图论基础知识,4、图的遍历,：,从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组,visitedi，,未访问时值为,false，,访问一次后就改为,true。,图的遍历分为深度优先遍历和广度（宽度）优先遍历两种方法。,图的深度优先遍历：,类似于树的先序遍历。从图中某个顶点,V,i,出发，访问此顶点并作已访问标记，然后从,V,i,的一个未被访问过的邻接点,V,j,出发再进行深度优先遍历，当,V,i,的所有邻接点都被访问过时，则退回到上一个顶点,V,k,，,再从,V,k,的另一个未被访问过的邻接点出发进行深度优先遍历，直至图中所有顶点都被访问到为止。,常州市第一中学 林厚从,图论算法与实现,一、图论基础知识,4、图的遍历,：,左图从顶点,a,出发，进行深度优先遍历的结果为：,a，b，c，d，e，g，f,右图从,V,1,出发进行深度优先遍历的结果为：,V,1,，V,2,，V,4,，V,8,，V,5,，V,3,，V,6,，V,7,对,下面两个图分别进行深度优先遍历，写出遍历结果。注意：分别从,a,和,V1,出发。,常州市第一中学 林厚从,图论算法与实现,一、图论基础知识,4、图的遍历,：,对于一个连通图，深度优先遍历的递归过程如下：,Procedure,dfs,(i:integer)；,图用邻接矩阵存储,Begin,访问顶点,i；,Visitedi:=True；,For j:=1 to n do ,按深度优先搜索的顺序遍历与,i,相关联的所有顶点,Begin,If(Not Visitedj)and(ai,j=1)Then,dfs,(j)；,End；,End；,以上,dfs,(i),的时间复杂度为,O（n*n）。,对于一个非连通图，调用一次,dfs,(i)，,即按深度优先顺序依次访问了顶点,i,所在的（强）连通分支，所以只要在主程序中加上：,for i:=1 to n do ,深度优先搜索每一个未被访问过的顶点,if not Visited（I)then,dfs,(i);,常州市第一中学 林厚从,图论算法与实现,一、图论基础知识,4、图的遍历,：,图的宽（广）度优先遍历：,类似于树的按层次遍历。从图中某个顶点,V,0,出发，访问此顶点，然后依次访问与,V,0,邻接的、未被访问过的所有顶点，然后再分别从这些顶点出发进行广度优先遍历，直到图中所有被访问过的顶点的相邻顶点都被访问到。若此时图中还有顶点尚未被访问，则另选图中一个未被访问过的顶点作为起点，重复上述过程，直到图中所有顶点都被访问到为止。,对,上面两个图分别从,a,和,V1,出发进行宽度优先遍历，写出遍历结果。,常州市第一中学 林厚从,图论算法与实现,一、图论基础知识,4、图的遍历,：,对,上面两个图分别从,a,和,V1,出发进行宽度优先遍历，写出遍历结果。,a，b，d，e，f，c，g,V,1,，V,2,，V,3,，V,4,，V,5,，V,6,，V,7,，V,8,常州市第一中学 林厚从,图论算法与实现,一、图论基础知识,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；,常州市第一中学 林厚从,