图及其应用一.pptx
《图及其应用一.pptx》由会员分享,可在线阅读,更多相关《图及其应用一.pptx(79页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、2、无向图和有向图、无向图和有向图无向图:在图在图G=G=(V V,E E)中,如果对于任意的)中,如果对于任意的a a,bVbV,当,当(a(a,b)Eb)E时,必有(时,必有(b b,a a)E E(即关系(即关系R R对称),对称图为无向对称),对称图为无向图。图。在一无向图中用不带箭头的边连接两个有关联的顶点。在一无向图中用不带箭头的边连接两个有关联的顶点。V=V1,V2,V3,V4,V5E=(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)第1页/共79页有向图:有向图:如果对于任意的如果对于任意的a a,bVbV,当,当(
2、a(a,b)Eb)E时时 ,(b(b,a)Ea)E未必成未必成立,则称此图为有向图。立,则称此图为有向图。在有向图中,通常用带箭头的边连接两个有关联的结点。在有向图中,通常用带箭头的边连接两个有关联的结点。V=V1,V2,V3,V4 V=V1,V2,V3,V4 E=,E=,第2页/共79页顶点的度:顶点的度:无向图:与顶点关联的边的数目。无向图:与顶点关联的边的数目。有向图:等于该顶点的入度与出度之和。有向图:等于该顶点的入度与出度之和。入度入度以该顶点为终点的边的数目和以该顶点为终点的边的数目和出度出度以该顶点为起点的边的数目和以该顶点为起点的边的数目和 度数为奇数的顶点叫做奇点,度数为偶数
3、的点叫做偶点。度数为奇数的顶点叫做奇点,度数为偶数的点叫做偶点。3 3、顶点的度、顶点的度第3页/共79页 练习题:1.假设我们用d=(a1,a2,.,a5),表示无向图G的5个顶点的度数,下面给出的哪(些)组d 值合理()。A)5,4,4,3,1 B)4,2,2,1,1 C)3,3,3,2,2 D)5,4,3,2,1 E)2,2,2,2,22.无向图G有16条边,有3个4度顶点、4个3度顶点,其余顶点的度均小于3,则G至少_个顶点。第4页/共79页4 4、路径和连通集路径和连通集 在在图图G=G=(V V,E E)中中,如如果果对对于于结结点点a a,b b,存存在在满满足足下下述述条条件的
4、结点序列件的结点序列x x1 1x xk k(k1)(k1)x x1 1=a=a,x xk k=b=b (x(xi i,x xi+1i+1)E i=1E i=1k-1k-1则则称称结结点点序序列列x x1 1=a=a,x x2 2,x xk k=b=b为为结结点点a a到到结结点点b b的的一一条条路路径径,而而路路径径上上边边的的数数目目k-1k-1(或或者者沿沿路路径径各各边边权权值值之之和和)称称为为该该路路径的长度,并称结点集合径的长度,并称结点集合xx1 1,x xk k 为连通集。为连通集。V1,v2,v5,v4第5页/共79页5 5、简单路径和回路、简单路径和回路如如果果一一条条
5、路路径径上上的的结结点点除除起起点点x x1 1和和终终点点x xk k可可以以相相同同外外,其其它它结结点点均均不不相相同同,则则称称此此路路径径为为一一条条简简单单路路径径。图图(a)(a)中中v v1 1vv2 2vv3 3是是一一条条简简单单路路径径,v v1 1vv3 3vv4 4vv1 1vv3 3不不是简单路径。是简单路径。x x1 1=x=xk k的的简简单单路路径径称称为为回回路路(也也称称为为环环)。例例如如图图(b)(b)中中,v v1 1vv2 2vv1 1为一条回路。为一条回路。第6页/共79页例157324G26例245136G1路径:1,2,3,5,6,3路径长度
6、:5简单路径:1,2,3,5回路:3,5,6,3路径:1,2,5,7,6,5,2,3路径长度:7简单路径:1,2,5,7,6回路:1,2,3,1第7页/共79页二、图的存储结构(教材二、图的存储结构(教材P79P79)图的邻接矩阵表示法图的邻接矩阵表示法 邻邻接接矩矩阵阵是是表表示示结结点点间间相相邻邻关关系系的的矩矩阵阵。若若G=G=(V V,E E)是是一一个个具具有有n n个个结结点点的的图图,则则G G的的邻邻接接矩矩阵阵是是如如下下定定义义的的二二维维数数组组a a,其其规规模模为为n*nn*n 1(1(或权值或权值)表示表示 顶点顶点i i和顶点和顶点j j有边有边(i(i和和j
7、j的路程的路程)Aij=Aij=0 0(或(或)表示顶点表示顶点i i和顶点和顶点j j无边无边 二维数组的行、列号表示顶点编号第8页/共79页上图中的图上图中的图G G1 1和图和图G G2 2对应的相邻矩阵分别为:对应的相邻矩阵分别为:无向带权图的邻接(代价)矩阵表示有向无权图的邻接矩阵表示第9页/共79页邻接矩阵的特点:1)无向图的邻接矩阵是对称的,而有向图则不是。2)邻接矩阵方便度数的计算。用邻接矩阵表示图:(1)容易判定任意两个结点之间是否有边相联;(2)容易求得各个结点的度数。对于无权无向图的邻接矩阵,第i行元素值的和就是Vi的度数;对于无权有向图的邻接矩阵,第i行元素值的和就是V
8、i的出度,第i列元素值的和就是Vi的入度;对于有权无向图的邻接矩阵,第i行(或第i列)中元素值0的元素个数就是Vi的度数;对于有权有向图的邻接矩阵,第i行中元素值0的元素个数就是Vi的出度;第i列元素值0的元素个数就是Vi的入度。第10页/共79页例1452375318642各顶点的度是多少?0618360240120078400530750第11页/共79页读入数据构造邻接矩阵(P80)竞赛题中一般图的数据是以这种方式给出的:题中会指定顶点数的最大值,以便于定义一个全局二维数组作为邻接矩阵数据文件的第1行一般是图的顶点个数N以及边数M接下来一般有M行,每行有2个或3个整数,描述了每条边的信息
9、:如果是2个整数i,j,则一般表示顶点i和顶点j有一条边相连如果是3个整数i,j,k,则一般表示顶点i和顶点j相连的权值为k针对图数据的这种结构,我们会用如下的代码来构造邻接矩阵:第12页/共79页const int MAXN=201;/最大顶点数int aMAXNMAXN,n,m,i,j,k,x;scanf(%d%d,&n,&m);for(i=1;i=m;i+)/读入m条边scanf(%d%d,&j,&k);ajk=1;/若是有向图,则只赋值ajkakj=1;/若是无向图,则一定要赋值akj如果是构造带权图,则上述for 语句中的代码改为:scanf(%d%d,&j,&k,&x);ajk=x
10、;/若是有向图,则只赋值ajkakjl=x;/若是无向图,则一定要赋值akj第13页/共79页邻接矩阵主对角线元素的处理在竞赛中很少有图数据是顶点带自环边的,因此邻接矩阵的主对角线元素aii(1=i=n)一般都是0。在前面讲的邻接矩阵的构造方法中,如果顶点i,j之间没有边,则aij也表示为0。在大多数图的算法中,不区别这两种值为0的情况是可以的。而在某些图算法中,必须要区别主对角线元素和其它非主对角线元素,这时就用另外的特殊值来表示无边相连的情况。特殊值一般取一个很大的正数(或负数),实现实现代码如下:第14页/共79页const int BIG=99999999;/表示无穷大for(i=1;
11、i=n;i+)/初始化 for(j=1;j=n;j+)aij=BIG;aii=0;for(i=1;i=m;i+)/读入边数据scanf(%d%d%d,&j,&k,&x);ajk=x;akj=x;/这句无向图才要 邻接矩阵的优缺点见教材P80判断i,j有无边相连:O(1)找i的邻接点,计算入度、出度:O(n)空间复杂性高:O(n2)第15页/共79页边集数组表示法(教材P80)一个一维数组存储图每个元素表示一条边:起点、终点、权值(如果有的话)适用于:对边进行依次处理的算法,适合存储顶点多但边很少的稀疏图缺点:判断i,j有无边相连:O(E)找i的邻接点,计算入度、出度:O(E)优点:结构简单第1
12、6页/共79页边集数组表示法的实现const int MAXEDGE=2000;struct node int s,t;/边的起点和终点int w;/边的权值node edgeMAXEDGE;int n,m,i,j,k,x;scanf(%d%d,&n,&m);for(i=1;i=m;i+)scanf(%d%d%d,&j,&k,&x);edgei.s=j;edgei.t=k;edgei.w=x;第17页/共79页邻接表表示法(P81)邻接表表示法是指对图中的每个顶点Vi(1=i=n)建立一个邻接关系的单链表,并把它们的表头指针用一维数组存储起来的一种表示方法。为每个顶点Vi建立的单链表,是表示以
13、该顶点为起点的所有边的信息。以下图(教材图52)为例,顶点v1与v2、v3、v5相邻,因此在v1的单链表里就包含3条边的信息。v1v2v3v4v5524101183253853顶点v1的单链表有3个结点,表示有3条边与v1相接,有3个顶点(v2、v3、v5)是v1的邻接点不表示v2与v3相邻,v3与v5相邻第18页/共79页邻接表表示法(P81)一维指针数组存储了每个顶点的单链表的头指针。一般就用数组下标表示了起点编号。例如v1单链表的头指针就存储在adj1中。下图的完整邻接表如下所示:v1v2v3v4v552410118325385315325618225431051113265114103
14、412345第19页/共79页邻接表的数据结构const int MAXV=201;/最大顶点数struct node int v;/邻接点序号 int wt;/权值,如果是带权图的话 node*next;/邻接单链表指针;node*adjMAXV;/每个顶点建一个单链表构造邻接表int n,m;/n表示读入的顶点个数,m表示读入的边条数第20页/共79页创建邻接表void createlist()/创建邻接表 int i,j,k,x;node*p;scanf(%d%d,&n,&m);/读入顶点数和边数 for(i=1;i=n;i+)/初始化每个顶点的边表为NULL adji=NULL;for
15、(i=1;iv=k;/j的邻接点是k p-wt=x;/边的权值是x p-next=adj j;/新节点插在顶点j的边表的表头位置 adj j=p;/以下是无向图需要构造的对称边 p=new node;p-v=j;/k的邻接点是j p-wt=x;p-next=adjk;/新节点插在顶点k的边表的表头位置 adjk=p;第21页/共79页邻接表的优缺点(P82)便于查找后继顶点、以该点为起点的边、出度。不便于查找前趋顶点、以该点为终点的边、入度。解决办法:建立逆邻接表,即把以某顶点为终点的顶点放在一个单链表中。和邻接矩阵相比,构造邻接表的编程复杂性要高一些,但是查找后继顶点的效率要高O(e/n)v
16、s.O(n)。如果边比较稀疏,显然用邻接表存储图比较好。第22页/共79页编程练习求一个有向图中指定顶点的出度。输入数据:第1行:2个空格分开的整数n(2=n=200)和m(10=m=20000),分别表示图的顶点数和边数。第2.m+1行:每行2个空格分开的整数i,j,i表示一条边的起点,j表示终点。第m2行:1个整数k(2=k=n),表示指定的顶点。输出数据:第1行:1个整数od,表示顶点k的出度。要求:分别用邻接矩阵和邻接表存储图。第23页/共79页三、三、图的遍历图的遍历给出一个图给出一个图G G和其中任意一个结点和其中任意一个结点V V,从,从V V出发访问出发访问G G中所有结中所有
17、结点,每一个结点被访问一次(不是只经过一次),这就叫图点,每一个结点被访问一次(不是只经过一次),这就叫图的遍历。的遍历。通常有两种遍历方法:通常有两种遍历方法:深度优先搜索深度优先搜索dfsdfs 广度优先搜索广度优先搜索bfsbfs 第24页/共79页1 1、深度优先搜索、深度优先搜索DFSDFS方法:从图的某一顶点V1出发,访问此顶点;然后依次从V1的未被访问的邻接点出发,深度优先遍历图,直至图中所有和V1相通的顶点都被访问到;若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问为止。为了避免重复访问某个顶点,设一个标志数组visit,顶
18、点i未访问时,visiti的值为false,访问后就改为true。V1V2V4V5V3V7V6V8例深度遍历:V1 V2 V4 V8 V5 V3 V6 V7可以从任一顶点出发进行DFS第25页/共79页V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历:V1 V2 V4 V8 V5 V6 V3 V7深度遍历:V1 V2 V4 V8 V5 V6 V3 V7第26页/共79页V1V2V4V5V3V7V6V8例深度遍历:V1 V2 V4 V8 V3 V6 V7 V5第27页/共79页在程序中实现深度优先搜索算法:从图的某一顶点V1出发,访问此顶点;然后依次从V1的未被访问的
19、邻接点出发,深度优先遍历图,直至图中所有和V1相通的顶点都被访问到。如何判别V的邻接点是否被访问?解决的办法是:为每个顶点设立一个“访问标志 visiti”如果图不连通,则一次DFS只能访问所有与V1连通的顶点。要对整个图进行遍历,则需要再任找一个尚未访问的顶点,再次DFS,直到所有顶点均被访问为止。第28页/共79页abchdekfg812345670FFFFFFFFF0 1 2 3 4 5 6 7 8T T T T T T T T Tach d kfe bgachkfedbg访问标志访问标志:访问次序访问次序:例如:achdkfe第29页/共79页参考代码/从顶点i出发进行深度优先搜索,邻
20、接表实现/适用于有向图和无向图void dfs(int i)node*p;cout v=false)/如果邻接点未访问 dfs(p-v);/则对其递归DFS p=p-next;/取下一个邻接点 第30页/共79页参考代码void dfstravel()/对图进行深度优先遍历 int i;memset(visit,0,sizeof(visit);/清访问标志 for(i=1;i=n;i+)if(!visiti)dfs(i);第31页/共79页DFS的应用1 1、犯罪团伙、犯罪团伙 警察抓到了警察抓到了n n个罪犯,警察根据经验知道他们属于不同的个罪犯,警察根据经验知道他们属于不同的犯罪团伙,却不
21、能判断有多少个团伙,但通过警察的审讯,知犯罪团伙,却不能判断有多少个团伙,但通过警察的审讯,知道其中的一些罪犯之间相互认识,已知同一犯罪团伙的成员之道其中的一些罪犯之间相互认识,已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系,确定犯罪团伙的数量。已知罪犯的编据已知罪犯之间的关系,确定犯罪团伙的数量。已知罪犯的编号从号从1 1至至n n。输入:输入:第一行:第一行:n n(=5000,=5000,罪犯数量),罪犯数量),m m(5000050000,关系数量),关系数量)以下以下m m行:每
22、行两个数:行:每行两个数:i i 和和j j,中间一个空格隔开,表示罪犯,中间一个空格隔开,表示罪犯i i和罪犯和罪犯j j相互认识。相互认识。输出:输出:一个整数,犯罪团伙的数量。一个整数,犯罪团伙的数量。第32页/共79页样例输入:11 8 1 24 35 41 35 67 105 108 9输出:3说明:共三个犯罪团伙。第33页/共79页分析把人处理成顶点,把认识关系处理成边,犯罪团伙构成一个图(有向还是无向?)则根据输入数据可以构造一个邻接表(可以用邻接矩阵吗?如果不能请说明原因)。从1到n枚举顶点Vi,从Vi进行DFS,则能找到一个团伙。然后再另选一个未访问的顶点,再次DFS,直到所
23、有顶点均被访问。最后,调用DFS的次数就是团伙的个数。第34页/共79页const maxn=1000;var a:array1.maxn,1.maxnof longint;visited:array1.maxnof 0.1;t:array1.maxnof char;n,m,i,s:longint;procedure init;var i,x,y:longint;begin assign(input,group5.in);reset(input);readln(n);readln(m);for i:=1 to m do begin readln(x,y);ax,y:=1;ay,x:=1;end
24、;close(input);end;procedure dfs(i:longint);var j:longint;begin visitedi:=1;for j:=1 to n do if(ai,j=1)and(visitedj=0)then dfs(j);end;Begin init;s:=0;for i:=1 to n do visitedi:=0;for i:=1 to n do if visitedi=0 then begin dfs(i);inc(s);end;writeln(s);end.第35页/共79页12354672 2、哈密顿路、哈密顿路 邮递员在送信时,为了节省路途,自己
25、规定:每次总是从n个村子中选择其中一个合适的村子出发,途经每个村子仅且经过一次,送完所有的信。已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线。输入:第一行:整数n(2=n=200):村子的个数。接下来是一个n*n的0、1矩阵,表示n个村子的连同情况,如:ai,j=1,表示第i和第j个村子之间有路可走,如果ai,j=0,表示他们之间无路可走。输出:一条可行的路线输入:70 1 0 1 1 0 01 0 1 0 1 0 00 1 0 0 0 0 11 0 0 0 0 0 01 1 0 0 0 1 00 0 0 0 1 0 10 0 1 0 0 1 0输出:输出:2 3 7 6 5 1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 及其 应用
限制150内