图论基础知识

常州市第一中学林厚从图论算法与实现一、图论基础知识二、无向图的传递闭包问题三、生成树与最小生成树问题四、最短路径问题五、拓扑排序与关键路径六、图论模型的建立七、匹配八、最大流常州市第一中学林厚从图论算法与实现一、图论基础知识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，如果存在一些顶点序列x1=a,x2,……,xk=b(k1)，且（xi,xi+1）∈E，i=1,2…k-1，则称顶点序列x1,x2,……,xk为顶点a到顶点b的一条路径，而路径上边的数目（即k-1）称为该路径的长度。并称顶点集合{x1,x2,……,xk}为一个连通集。简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均不相同，则称此路径为一条简单路径；起点和终点相同的简单路径称为回路（或环）。常州市第一中学林厚从图论算法与实现一、图论基础知识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条边）：邻接矩阵边集数组邻接表优点直观方便,A[i，j]时间O（1）存储稀疏图时，空间效率比较好，也比较直观便于查找任一顶点的关联边及关联点,查找运算的时间复杂性平均为O(e/n)缺点存储稀疏图，会造成很大的空间浪费不适合对顶点的运算和对任意一条边的运算要查找一个顶点的前驱顶点和以此顶点为终点的边、以及该顶点的入度就不方便了，需要扫描整个表，时间复杂度为O（n+e）。可以用十字邻接表改进适用场合处理1个顶点的度和关联边，O（n）适合于存储稀疏图和那些对边依次进行处理的运算对任一顶点的关联边（顶点）进行不断、重复的运算空间复杂度O（n*n）O（3e）≈O（6e+2n）常州市第一中学林厚从图论算法与实现一、图论基础知识4、图的遍历：从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visited[i]，未访问时值为false，访问一次后就改为true。图的遍历分为深度优先遍历和广度（宽度）优先遍历两种方法。图的深度优先遍历：类似于树的先序遍历。从图中某个顶点Vi出发，访问此顶点并作已访问标记，然后从Vi的一个未被访问过的邻接点Vj出发再进行深度优先遍历，当Vi的所有邻接点都被访问过时，则退回到上一个顶点Vk，再从Vk的另一个未被访问过的邻接点出发进行深度优先遍历，直至图中所有顶点都被访问到为止。常州市第一中学林厚从图论算法与实现一、图论基础知识4、图的遍历：左图从顶点a出发，进行深度优先遍历的结果为：a，b，c，d，e，g，f右图从V1出发进行深度优先遍历的结果为：V1，V2，V4，V8，V5，V3，V6，V7对下面两个图分别进行深度优先遍历，写出遍历结果。注意：分别从a和V1出发。常州市第一中学林厚从图论算法与实现一、图论基础知识4、图的遍历：对于一个连通图，深度优先遍历的递归过程如下：Proceduredfs(i:integer)；{图用邻接矩阵存储}Begin访问顶点i；Visited[i]:=True；Forj:=1tondo{按深度优先搜索的顺序遍历与i相关联的所有顶点}BeginIf(NotVisited[j])and(a[i,j]=1)Thendfs(j)；End；End；以上dfs(i)的时间复杂度为O（n*n）。对于一个非连通图，调用一次dfs(i)，即按深度优先顺序依次访问了顶点i所在的（强）连通分支，所以只要在主程序中加上：fori:=1tondo{深度优先搜索每一个未被访问过的顶点}ifnotVisited（I)thendfs(i);常州市第一中学林厚从图论算法与实现一、图论基础知识4、图的遍历：图的宽（广）度优先遍历：类似于树的按层次遍历。从图中某个顶点V0出发，访问此顶点，然后依次访问与V0邻接的、未被访问过的所有顶点，然后再分别从这些顶点出发进行广度优先遍历，直到图中所有被访问过的顶点的相邻顶点都被访问到。若此时图中还有顶点尚未被访问，则另选图中一个未被访问过的顶点作为起点，重复上述过程，直到图中所有顶点都被访问到为止。对上面两个图分别从a和V1出发进行宽度优先遍历，写出遍历结果。常州市第一中学林厚从图论算法与实现一、图论基础知识4、图的遍历：对上面两个图分别从a和V1出发进行宽度优先遍历，写出遍历结果。a，b，d，e，f，c，gV1，V2，V3，V4，V5，V6，V7，V8常州市第一中学林厚从图论算法与实现一、图论基础知识4、图的遍历：深度优先遍历与宽度优先遍历的比较：深度优先遍历实际上是尽可能地走“顶点表”；而广度优先遍历是尽可能沿顶点的“边表”进行访问，然后再沿边表对应顶点的边表进行访问，因此，有关边表的顶点需要保存(用队列，先进先出)，以便进一步进行广度优先遍历。下面是广度优先遍历的过程：常州市第一中学林厚从图论算法与实现一、图论基础知识4、图的遍历：时间：O（n*n）Procedurebfs(i:integer)；{宽度优先遍历，图用邻接矩阵表示}Begin访问顶点i；Visited[i]:=true;顶点i入队q；while队列q非空dobegin从队列q中取出队首元素v；forj:=1tondobeginif(notVisited[j])and(a[v,j]=1)thenbegin访问顶点j；Visited[j]:=true;顶点j入队qend;end;end;End；