《图论算法课件》由会员分享，可在线阅读，更多相关《图论算法课件（41页珍藏版）》请在金锄头文库上搜索。
1、图,山东聊城第一中学 张凯,图的定义,简单讲，一个图是由一些点和这些点之间的连线构成的。严格意义讲，图是一种数据结构，定义为：graph=(V,E),V是点（称为“顶点”）的非空有限集合，E是线（称为“边”）的集合，边一般用(Vx,Vy)表示，其中Vx,Vy属于V。,无向图和有向图,如果边是没有方向的，称此图为“无向图”，如果边是有方向（带箭头）的，则称此图为“有向图”。有向图中的边又称为弧，起点称为弧头，终点称为弧尾。,带权图,一个图中的两顶点不仅是关联的，而且在边上还标明了数量关系，边上带有权的图称为带权图，也称为网（络）。,度,图中与某个顶点相关联的边的数目，称为该顶点的度。度为奇数的顶
2、点成为奇点，度为偶数的顶点称为偶点。在有向图中，把以顶点v为终点的边的数目称为顶点v的入度，把以顶点u为起点的边的数目称为顶点u的出度，出度为0的顶点称为终端顶点。,子图,设有两个图G=(V,E)和G=(V,E)，若V是V的子集，E是E的子集，则称G为G的子图。,路（径）,在一个G=(V,E)的图中，从顶点v到顶点v的一条路径是一个顶点序列vi,0，vi,1，vi,2，vi,m，其中vi,0=v，vi,m=v。路径长度是指路径上的边或弧的数目。序列中顶点不重复出现的路径称为简单路径，顶点v和顶点v相同的路径称为回路（或环）。除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路
3、（或简单环）。,连通图,在无向图g中，如果从顶点u到顶点v有路径，则称u和v是连通的。如果对于图g中的任意两个顶点u和v都是连通的，则称图g是连通图，否则称为非连通图。 在有向图g中，如果对于任意两个顶点u和v，从u到v和从v到u都存在路径，则称图g是强连通图。,图的存储结构,邻接矩阵表示法 设图中总顶点数为n，那么我们定义一个数组a1n,1n，其中ai,j记录从顶点i到顶点j的边的信息。如果把这个数组以n*n的形式输出，我们将得到一个矩阵。无向图的邻接矩阵是对称的，而有向图则不一定。 采用邻接矩阵表示图，直观方便，很容易查找图中任两个顶点i和j之间有无边，以及边上的权值，只要看Ai,j的值即
4、可，因为可以根据i,j的值随即查找存取，所以时间复杂性为O(1)。也很容易计算一个顶点的度（或入度、出度）和邻接点，其时间复杂性为O(n)。但是，邻接矩阵表示法的空间复杂性O(n*n)，如果用来表示稀疏图，则会造成很大的空间浪费。,图的存储结构,邻接矩阵表示法 var a:array 1n,1n of longint; begin readln(n); for i:=1 to n do for j:=1 to n do read(aij); end.,图的存储结构,边集表示法 边集数组是利用一维数组存储图中所有边的一种图的表示方法,每个数组元素存储一条边的起点。终点和权值。在边集数组中查找一条
5、边或一个顶点的度都需要扫描整个数组，所以其时间复杂度为O(e),但如果我们用前向星进行优化，就会使效率大大提高。从空间复杂性上讲，边集数组适合于存储稀疏图。,图的存储结构,边集表示法 type bian=record x,y,z:longint; end; var a:array1e of bian; begin readln(e); for i:=1 to e do readln(ai.x,ai.y,ai.z); end.,图的存储结构,邻接表表示法 邻接表表示法是对图中的每个顶点vi建立一个邻接关系的单链表，并把它们的表头指针用一维向量数组存储起来的一种图的表示方法。为每个顶点vi建立的单
6、链表，是表示以该顶点为起点的所有边的信息（包括一个终点序号，一个权值和一个链接域）。,图的存储结构,邻接表表示法 如下是一个例子：,图的存储结构,邻接表表示法 type bian=record y,z:longint; end; var a:array 1e of bian; /邻接表数组 next:array1e of longint; /指针域 head:array1n of longint; /头指针 begin readln(n,e); for i:=1 to e do begin readln(x,ai.y,ai.z); nexti:=headx; headx:=i; end; en
7、d.,图的遍历,深度优先遍历（dfs） 广度优先遍历（bfs）,图的常用算法,最小生成树 最短路径、差分约束系统 拓扑排序 强连通分量 欧拉路,最小生成树,如果图G=(V,E)是一个连通的无向图，则把它的全部顶点V和一部分E构成一个子图G，即G=(V,E)，且边集E能将图中所有顶点连通又不形成回路，则称子图G是图G的一棵生成树。可以证明，n个顶点的连通图的生成树必定含有n-1条边。对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。,最小生成树,Prim算法 （1）设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集； （2）选定图中的一
8、个顶点K,从K开始生成最小生成树，将K加入到集合S中； （3）重复下列操作，直到选取了K-1条边： 选取一条权值最小的边(X,Y)，其中XS，not(YS)；将顶点Y加入集合S，边(X,Y)加入集合TE； （4）得到最小生成树T=(S,TE),最小生成树,Kruskal算法 设最小生成树为T=(V,TE)，设置边的集合TE的初始状态为空集。将图G中的边按权值从小到大排好序，然后从小的开始依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树形成回路，则将其舍弃；如此进行下去，直到TE中包含n-1条边为止。最后的T即为最小生成树。,最小生成树,Krus
9、kal算法 Kruskal算法在实现过程中的关键和难点在于：如何判断欲加入的一条边是否与生成树中已保留的边形成回路？我们可以将顶点划分到不同的集合中，每个集合中的顶点表示一个无回路的连通分量。很明显，算法开始时，把所有n个顶点划分到n个集合中，每个集合只有一个顶点，表明顶点之间互不连通。当选取一条边时，若它的两个顶点分属于不同的集合，则表明此边连通了两个不同的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，因此这条边应该保留，且把它们作为一个连通分量，即把它的两个顶点所在的集合合并成一个集合。如果选取的一条边的两个顶点属于同一个集合，则此边应该舍弃，因为同一个集合中的顶
10、点是连通无回路的，若再加入一条边则必然产生回路。这里的集合可以使用并查集来实现。,并查集,并查集的实质就是集合，这个集合是一棵有着树的形式的集合。它支持两种操作：查找某个元素所在的集合，以及将两个集合合并。在并查集的定义中，我们设一个数组fa1n，fai表示第i个元素的父结点。集合的根节点i的fai设为0。查找操作就是顺着fa数组往上找到根结点，合并操作就是就一个集合的根结点的父结点设成另一个集合的根结点。,最短路径,在带权图G=(V,E)中，若顶点vi,vj是图G的两个顶点，从顶点vi到vj的路径长度定义为路径上的各条边的权值之和。从顶点vi到vj可能有多条路径，其中路径长度最小的一条路径成
11、为顶点vi到vj的最短路径。一般有两类最短路径问题：一类是求从某个顶点到其他顶点的最短路径；另一类是求图中每一对顶点间的最短路径。,最短路径,单源最短路径： Dijkstra算法 SPFA算法 多源最短路径： Floyed算法,单源最短路径,Dijkstra算法 用一个dist数组来表示源点S到各个顶点的距离估价。初始时将所有disti设为INTMAX，只有distS设为0，并将S设成访问过。然后不断从未访问的顶点中选出一个dist估价最小的顶点i，将i设成访问过，并从顶点i出发进行松弛操作。这里的松弛操作，是对其他没访问过的顶点j，如果disti+ai,jdistj就令distj=disti
12、+ai,j，即尝试着用i去减小j的距离估价dist，直到最终距离估价变成真实的最短路径。此时所有顶点都应当是已访问过的。,单源最短路径,SPFA算法 需要一个队列作为辅助。用一个dist数组来表示源点S到各个顶点的距离估价。初始时将所有disti设为INTMAX，只有distS设为0，并将S加入队列。然后每次取出队头元素，用它去对其他顶点进行松弛操作，如果对顶点i松弛操作成功，且i不在队列里面，就把它加入队尾。由于一个顶点可能多次入队，需要使用循环队列。直到队列为空算法结束。,多源最短路径,Floyed算法： 设数组a为图的邻接矩阵，而且我们已读入了图的边信息，我们可以直接对a数组进行Floy
13、ed算法。 for k:=1 to n do for i:=1 to n do for j:=1 to n do if ai,k+ak,jai,j then ai,j:=ai,k+ak,j; 这个算法的实质是一个动态规划，不过我们也没有必要究其本源，会用就行。,差分约束系统,为了便于大家理解差分约束系统是什么意思，我们先看一道题目。,【例题】工程规划,造一幢大楼是一项艰巨的工程，它是由N个子任务构成的，给他们分别编号1,2,.,N(5=N=1000)。由于对一些任务的起始条件有着严格的限制，所以每个任务的起始时间T1,T2,-,TN并不是很容易确定的。例如：挖掘完成后，紧接着就要打地基；但是混
14、凝土浇筑完成后，却要等待一段时间再去掉模板。 这种要求就可以用M(5=M=5000)个不等式来表示，不等式形如Ti-Tj=B代表i和j的起始时间必须满足的条件。每个不等式的右边都是一个常数B，这些常数可能不相同，但是他们都在区间(-100,100)内。,【例题】工程规划,你的任务就是写一个程序，当给定像上面那样的不等式后，找出一种可能的起始时间序列T1,T2,.,TN，或者判断问题无解。对于有解的情况，要使最早进行的那个任务和整个工程的起始时间相同，也就是说，T1,T2,.,TN中至少有一个为0。 输入：输入文件名为work.in，第一行是用空格隔开的两个正整数N和M，下面的M行每行有三个用空
15、格隔开的整数i,j,B对应着不等式Ti-Tj=B。 输出：输出文件名work.out，如果有可行的方案，那么输出N行，每行都有一个非负整数且至少有一个为0，按顺序表示每个任务的起始时间。如果没有可行的方案，就输出信息NO SOLUTION。,【例题】工程规划,两个样例：,题目分析,本题是使用“差分约束系统”解决的。题目让我们对一系列形如Ti-Tj=B的不等式求出一组可行解。如果将Ti-Tj=B变形可得Ti=Tj+B，他让我们联想到了一个东西，那就是松弛操作。我们可以将其转化成一个最短路问题，对于不等式Ti=Tj+B，我们加入一条从j到i的长度为B的路径。然后再加入一个结点S，并从S向所有结点连
16、一条长度为0的边。最后以S为源点做一遍SPFA。无解的情况就是没有最短路的情况，就是有负权环的情况，就是某个结点入队超过n次的情况。,拓扑排序,在日常生活中，一项大的工程可以看做是由若干个子工程组成的集合，这些子工程之间必定存在一些先后关系即某些子工程必须在其他一些子工程完成之后才能开始，我们可以用有向图来形象地表示这些子工程的先后关系，子工程为顶点，子工程之间的先后关系为有向边，这种有向图为“顶点活动网络”，又称“AOV”网。一个AOV网应该是一个有向无环图，即不应该带有回路，否则必定会有一些活动互相牵制，造成环中的活动都无法进行。把不带回路的AOV网 中的所有活动排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，这个过程称为“拓扑排序”，所得到的活动序列称为“拓扑序列”。,拓扑排序,其实，构造拓扑序列的拓扑排序算法思想很简单：只要选择一个入度为0的顶点并输出，然后从A
