图论算法(C 版)PPT课件

第四章图论算法,一对一和一对多的结构：在前边讲解的线性表中，每个元素之间只有一个直接前驱和一个直接后继，在树形结构中，数据元素之间是层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。图结构：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。图的应用极为广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。,一、图的定义及其术语图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。,对于图的定义，我们需要明确几个注意的地方：线性表中我们把数据元素叫元素，树中叫结点，在图中数据元素我们则称之为顶点(Vertex)。线性表可以没有数据元素，称为空表，树中可以没有结点，叫做空树，而图结构在国内大部分的教材中强调顶点集合V要有穷非空。线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图结构中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。,图的各种定义,无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边(Edge)，用无序偶数对(Vi,Vj)来表示。无向图：图中所有顶点间的边均是无向的。,上图G1是一个无向图，G1=V1,E1，其中V1=A,B,C,D，E1=(A,B),(B,C),(C,D),(D,A),(A,C)无序对(A,B)表示A和B之间的一条边(Edge)，因此(A,B)和(B,A)代表的是同一条边。,上图G2是一个无向图，G2=V2,E2，其中V2=A,B,C,D，E2=,有向边：若从顶点Vi到Vj的边有方向，则称这条边为有向边，也称为弧(Arc)，用有序偶数对来表示，Vi称为弧尾，Vj称为弧头。有向图：图中所有顶点间的边均是有向的。,简单图：在图结构中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。以下两个则不属于简单图：,稀疏图、稠密图、权有很少边或弧的图（ee;for(k=1;kijw;/读入两个顶点序号及权值gij=w;/对于不带权的图gij=1gji=w;/无向图的对称性,如果是有向图则不要有这句！return0;,建立邻接矩阵时，有两个小技巧:初始化数组大可不必使用两重for循环。1)如果是int数组，采用memset(g,0 x7f,sizeof(g)可全部初始化为一个很大的数(略小于0 x7fffffff)，使用memset(g,0,sizeof(g)，全部清为0，使用memset(g,0 xaf,sizeof(g)，全部初始化为一个很小的数。2)如果是double数组，采用memset(g,127,sizeof(g);可全部初始化为一个很大的数1.38*10306，使用memset(g,0,sizeof(g)全部清为0.,2.数组模拟邻接表存储邻接矩阵看上去是个不错的选择，首先是容易理解，第二是索引和编排都很舒服但是我们也发现，邻接矩阵适合于结点数较少的稠密图。如果用来表示稀疏图，则会造成很大的空间浪费。因此我们可以考虑另外一种存储结构方式，例如把数组与链表结合一起来存储，这种方式在图结构也适用，我们称为邻接表(AdjacencyList)。基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。图的邻接表存储法，又叫链式存储法。本来是要用链表实现的，但大多数情况下只要用数组模拟即可。,邻接表（有向图）邻接表的处理方法是这样：图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。,若是有向图，邻接表结构就是这样定义的。,有向图的邻接表：我们先来看下把顶点当弧尾建立的邻接表，这样很容易就可以得到每个顶点的出度：,但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接表：,此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。,对于带权值的网图，可以在边表结点定义中再增加一个数据域来存储权值即可：,邻接表（网）,在进行邻接表的输入时，可以直接使用邻接表的定义方式直接输入；也可由别的输入方式进行演变，课本上的就是利用边的顶点及其权值进行输入的,以下是用数组模拟邻接表存储的参考程序段：,constintN=maxn；/maxn表示图中最大顶点数constintE=maxe；/maxe图中最大边数structEdgeintu,v;/边所邻接的两个顶点intw;/边的权值intnext;/边指针，指向下一条边的内存地址edgeE;/静态内存，用于分配边intheadN;/表头intnum;/内存的指针voidinit()for(inti=0;iE;i+)headi=-1;/这里为什么要设为-1num=0;voidaddedge(intb,inte,intw)edgenum.u=b;edgenum.v=e;edgenum.w=w;edgenum.next=headb;headb=num+;,intmain()num_edge=0;scanf(%d%d,两种方法各有用武之地，需按具体情况，具体选用。,课本上的程序段#includeusingnamespacestd;constintmaxn=1001,maxm=100001;structEdgeintnext;/下一条边的编号intto;/这条边到达的点intdis;/这条边的长度edgemaxm;intheadmaxn,num_edge,n,m,u,v,d;voidadd_edge(intfrom,intto,intdis)/加入一条从from到to距离为dis的单向边edge+num_edge.next=headfrom;edgenum_edge.to=to;edgenum_edge.dis=dis;headfrom=num_edge;intmain()for(inti=1;i=m;i+)scanf(%d%d%d,i=edgei.next)/遍历从点1开始的所有边,【例题】求一个有向图中指定顶点的出度,【问题描述】如题【文件输入】第1行：2个空格分开的整数n(2=n=200)和m(10=m=20000)，分别表示图的顶点数和边数。第2.m+1行：每行2个空格分开的整数i，j，i表示一条边的起点，j表示终点。第m2行：1个整数k(2nm;for(i=1;ijk;ajk=1;intmain()init();cink;for(inti=1;i=n;i+)if(aki)ans+;coutansne;/读入顶点数目和边数for(i=1;ixy;AddEdge(x,y);/建图cink;for(intp=hk;p!=0;p=wp.next)ans+;coutansendl;,第二节图的遍历,一、深度优先与广度优先遍历从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visitedi，未访问时值为false，访问一次后就改为true。图的遍历分为深度优先遍历和广度优先遍历两种方法，两者的时间效率都是O(n*n)。,1.深度优先遍历深度优先搜索(DepthFirstSearch-DFS)遍历类似树的先序遍历，是树的先序遍历的推广。1算法思想设初始状态时图中的所有顶点未被访问，则：从图中某个顶点vi出发，访问vi；然后找到vi的一个邻接顶点vi1；：从vi1出发，深度优先搜索访问和vi1相邻接且未被访问的所有顶点；：转，直到和vi相邻接的所有顶点都被访问为止：继续选取图中未被访问顶点vj作为起始顶点，转(1)，直到图中所有顶点都被访问为止。,例如对右边的这个无向图深度优先遍历，假定先从1出发程序以如下顺序遍历：125，然后退回到2，退回到1。从1开始再访问未被访问过的点3，3没有未访问的邻接点，退回1。再从1开始访问未被访问过的点4，再退回1。起点1的所有邻接点都已访问，遍历结束。,下面给出的深度优先遍历的参考程序，假设图以邻接表存储voiddfs(inti)/图用数组模拟邻接表存储，访问点ivisitedi=true;/标记为已经访问过for(intj=1;j=numi;j+)/遍历与i相关联的所有未访问过的顶点if(!visitedgij)dfs(gij);主程序如下:intmain()memset(visited,false,sizeof(visited);for(inti=1;i=n;i+)/每一个点都作为起点尝试访问，因为不是从任何/一点开始都能遍历整个图的，例如下面的两个图。if(!visitedi)dfs(i);return0;,广度优先搜索BFS,广度优先搜索(BreadthFirstSearch-BFS)遍历类似树的按层次遍历的过程。1算法思想设初始状态时图中的所有顶点未被访问，则：从图中某个顶点vi出发，访问vi；：访问vi的所有相邻接且未被访问的所有顶点vi1，vi2，vim；：以vi1，vi2，vim的次序，以vij(1jm)依此作为vi，转；：继续选取图中未被访问顶点vk作为起始顶点，转，直到图中所有顶点都被访问为止。,下图是有向图的广度优先搜索遍历示例(浅色箭头)。上述图的BFS次序是：v1v2v4v3v5,用广度优先搜索算法遍历图与深度优先搜索算法遍历图的唯一区别是邻接点搜索次序不同，因此，广度优先搜索算法遍历图的总时间复杂度为O(n+e)。图的遍历可以系统地访问图中的每个顶点，因此，图的遍历算法是图的最基本、最重要的算法，许多有关图的操作都是在图的遍历基础之上加以变化来实现的。,【例题】无向图的BFS,【问题描述】一个无向图，从指定顶点出发进行BFS，求遍历得到的顶点序。【文件输入】第1行：2个空格分开的整数n(2=n=200)和m(10=m=20000)，分别表示图的顶点数和边数。第2.m+1行：每行2个空格分开的整数i，j，i表示一条边的起点，j表示终点。第m2行：1个整数k(1nm;memset(f,0,sizeof(f);for(i=1;ixy;axy=1;ayx=1;cinst;voiddfs(inti)/深搜DFSintj;couti;fi=1;for(j=1;jne;for(i=1;ixy;gyx=gxy=1;dux+;/统计每个点的度duy+;start=1;/如果有奇点，就从奇点开始寻找，这样找到的就是for(i=1;i=n;i+)/欧拉路。没有奇点就从任意点开始，if(dui%2=1)/这样找到的就是欧拉回路。(因为每一个点都是偶点)start=i;circuitpos=0;find_circuit(start);for(i=1;i=circuitpos;i+)coutcircuiti;coutendl;return0;,注意以上程序具有一定的局限性，对于下面这种情况它不能很好地处理：上图具有多个欧拉回路，而本程序只能找到一个回路。读者在遇到具体问题时，还应对程序作出相应的修改。,三、哈密尔顿环欧拉回路是指不重复地走过所有路径的回路，而哈密尔顿环是指不重复地走过所有的点，并且最后还能回到起点的回路。哈密顿通路（回路）与哈密顿图（Hamilton图）通过图G的每个结点一次，且仅一次的通路（回路），就是哈密顿通路（回路）.存在哈密顿回路的图就是哈密顿图美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密顿图。闭合的哈密顿路径称作哈密顿圈，含有图中所有顶点的路径称作哈密顿路径。,【例题1】哈密顿路问题,【问题描述】邮递员在送信时，为了节省路途，自己规定：每次总是从n个村子中选择其中一个合适的村子出发，途经每个村子仅且经过一次，送完所有的信。已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线。【文件输入】第1行：整数n(2=n=200)：村子的个数。接下来是一个n*n的0、1矩阵（每2个数之间有1个空格），表示n个村子的连通情况，如：ai,j=1，表示第i和第j个村子之间有路可走，如果ai,j=0，表示他们之间无路可走。【文件输出】只有一行为1个整数表示可行的方案总数。,#include#includeusingnamespacestd;inta201201,visit201,found,n,sum;voidinit()inti,j;scanf(%d,intmain()inti;init();found=0;sum=0;for(i=1;i=n;i+)memset(visit,0,sizeof(visit);visiti=1;dfs(i,1);if(found=0)printf(%d,0);elseprintf(%d,sum);return0;,使用简单的深度优先搜索，就能求出一张图中所有的哈密尔顿环。下面给出一段参考程序：,#include#includeusingnamespacestd;intstart,length,x,n;boolvisited101,v1101;intans101,num101;intg101101;voidprint()inti;for(i=1;i=length;i+)cout“”ansi;coutendl;,voiddfs(intlast,inti)/图用数组模拟邻接表存储，访问点i，last表示上次访问的点visitedi=true;/标记为已经访问过v1i=true;/标记为已在一张图中出现过ans+length=i;/记录下答案for(intj=1;j=numi;j+)if(gij=x/这里是回溯过程，注意v1的值不恢复。,intmain()memset(visited,false,sizeof(visited);memset(v1,false,sizeof(v1);for(x=1;x=n;x+)/每一个点都作为起点尝试访问，因为不是从任何一点开始都能找过整个图的if(!v1x)/如果点x不在之前曾经被访问过的图里。length=0;/定义一个ans数组存答案，length记答案的长度。dfs(0，x);return0;,【上机练习】,1、珍珠BEAD【问题描述】有n颗形状和大小都一致的珍珠，它们的重量都不相同。n为整数，所有的珍珠从1到n编号。你的任务