文档介绍：常州市第一中学林厚从图论算法与实现一、图论基础知识二、无向图的传递闭包问题三、生成树与最小生成树问题四、最短路径问题五、拓扑排序与关键路径六、图论模型的建立七、匹配八、最大流常州市第一中学林厚从图论算法与实现一、图论基础知识 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(k>1) ,且( x i,x i +1)∈E, i=1,2 … k-1 ,则称顶点序列 x 1 ,x 2,……,x k为顶点 a到顶点 b的一条路径,而路径上边的数目(即 k-1 )称为该路径的长度。并称顶点集合{x 1 ,x 2,……,x k}为一个连通集。简单路径:如果一条路径上的顶点除了起点和终点可以相同外,其它顶点均不相同,则称此路径为一条简单路径;起点和终点相同的简单路径称为回路(或环)。常州市第一中学林厚从图论算法与实现一、图论基础知识 2、图的基本概念: 路径和简单路径的举例: 左图 1—2—3是一条简单路径,长度为 2, 而1—3—4—1—3就不是简单路径; 右图 1—2—1为一个回路。常州市第一中学林厚从图论算法与实现一、图论基础知识 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条边): ≈O(6e+2n ) O(3e) O(n*n) 空间复杂度对任一顶点的关联边(顶点) 进行不断、重复的运算适合于存储稀疏图和那些对边依次进行处理的运算处理 1个顶点的度和关联边, O(n) 适用场合要查找一个顶点的前驱顶点和以此顶点为终点的边、以及该顶点的入度就不方便了,需要扫描整个表,时间复杂度为 O (n+e )。可以用十字邻接表改进不适合对顶点的运算和对任意一条边的运算存储稀疏图,会造成很大的空间浪费缺点便于查找任一顶点的关联边及关联点,查找运算的时间复杂性平均为 O(e/n) 存储稀疏图时,空间效率比较好,也比较直观直观方便,A[i ,j] 时间 O(1) 优点邻接表边集数组邻接矩阵常州市第一中学林厚从图论算法与实现一、图论基础知识 4、图的遍历: 从图中某一顶点出发系统地访问图中所有顶点,使每个顶点恰好被访问一次,这种运算操作被称为图的遍历。为了避免重复访问某个顶点,可以设一个标志数组 visited[i] , 未访问时值为 false , 访问一次后就改为 true 。图的遍历分为深度优先遍历和广度(宽度)优先遍历两种方法。图的深度优先遍历: 类似于树的先序遍历。从图中某个顶点 V i出发, 访问此顶点并作已访