图的基本概念及拓扑排序

图的基本概念及拓扑排序第一页，共五十三页，2022年，8月28日什么是图？什么是图?可用一句话概括，即：图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型.因为它显得太抽象，不便于理解，所以有必要给出另外的回答.第二页，共五十三页，2022年，8月28日1图的基本术语图：记为G＝(V,E)

其中：V

是G的顶点集合，是有穷非空集；E

是G的边集合，是有穷集。有向图：无向图：图G中的每条边都是有方向的；图G中的每条边都是无方向的；若

n个顶点的无向图有

n(n-1)/2条边,

称为无向完全图若

n个顶点的有向图有n(n-1)条边,称为有向完全图V=vertexE=edge第三页，共五十三页，2022年，8月28日例：判断下列4种图形各属什么类型？无向无向图(树)有向图有向完全图完全图第四页，共五十三页，2022年，8月28日稀疏图：

稠密图：设有两个图G＝(V,E)和G’＝(V’,E’)。若V’V且E’E,则称图G’是图G的子图。子图：边较少的图。通常边数<<n2边很多的图。无向图中，边数接近n(n-1)/2；

有向图中，边数接近n(n-1)补图：

定义1：设图G1=<V1，E1>和图G2=<V2，E2>是图G=<V，E>的子图.如果E2=E-E1且G2=<E2>，则称图G2是相对于图G的子图G1的补图.定义2：给定图G=<V，E>，若存在图G1=<V，E1>，并且E1∩E=和图<V，E1∪E>是完全图，则G1称为相对于完全图的G的补图，简称G1是G的补图.

第五页，共五十三页，2022年，8月28日带权图：即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。＝带权图网络：

路径：在图G＝(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vivp1vp2...vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应当是属于E的边。非带权图的路径长度是指此路径上边的条数；带权图的路径长度是指路径上各边的权之和。

路径长度：第六页，共五十三页，2022年，8月28日连通图：在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。强连通图：在有向图中,

若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。

非强连通图的极大强连通子图叫做强连通分量。第七页，共五十三页，2022年，8月28日生成树：邻接点：

顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。

顶点v的入度是以v为终点的有向边的条数,记作ID(v);

顶点v的出度是以v为始点的有向边的条数,记作OD(v)。若(u,v)是E(G)中的一条边，则称u与v互为邻接顶点度、入度和出度：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。如果在生成树上添加1条边，必定构成一个环。若图中有n个顶点，却少于n-1条边，必为非连通图。最小生成树：若无向连通带权图G=<V,E,W>,T是G的一棵生成树，T的各边权之和称为T的权，记做W（T），G的所有生成树中权值最小的生成树称为最小生成树。最小生成树算法：Prim算法和kruskal算法第八页，共五十三页，2022年，8月28日简单路径：路径上各顶点v1,v2,...,vm

均不互相重复。回路：例：若路径上第一个顶点v1

与最后一个顶点vm

重合，则称这样的路径为回路或环。第九页，共五十三页，2022年，8月28日图的数学表示

点:用整数0,1,2,…,V-1表示

边:用无序数对(u,v)表示,或者表示成u-v第十页，共五十三页，2022年，8月28日7.2图的存储结构重点介绍：邻接矩阵(数组)表示法邻接表(链式)表示法主要有下面四种方法：邻接矩阵邻接表十字链表多重链表第十一页，共五十三页，2022年，8月28日一、邻接矩阵（数组）表示法建立一个邻接矩阵（表示各个顶点之间关系）。设图A=(V,E)有n

个顶点，则图的邻接矩阵是一个二维数组A.Edge[n][n]，定义为：1235v44A例1：邻接矩阵：A.Edge=（

12

345

）1234500

0

0000

0000

0000000000000001

0

1010

1010

101110101011

1001

0

1010

1

010

1

01110101011

10顶点表：第十二页，共五十三页，2022年，8月28日例2：有向图的邻接矩阵v1v2v3v4A邻接矩阵：A.Edge=(

v1v2

v3v4)v1v2v3v400

0

000

000

0000000注：在有向图的邻接矩阵中，第i行含义：以结点vi为起点的边(即出边）；第i列含义：以结点vi为终点的弧(即入边）。顶点表：01

1

000

000

0

01

1

00001

1

000

000

0

01

1

000第十三页，共五十三页，2022年，8月28日特别讨论：网（即有权图）的邻接矩阵定义为：A.Edge[i][j]=Wij

<vi,vj>或（vi,vj）∈VR∞

无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：邻接矩阵：N.Edge=(12

3456)顶点表：∞

5

∞

7

∞

∞∞

∞

4

∞

∞

∞

8

∞

∞

∞∞

9∞

∞

5∞

∞

6∞

∞

∞

5

∞

∞

3

∞

∞∞

1

∞第十四页，共五十三页，2022年，8月28日图的邻接矩阵表示示例intadjlist[max_vex_num][max_vex_num];

说明：adjlist[i][j]若无权图无重边则直接用01表示Ij两点是否直接邻接若无权图有重边则直接用01….表示是Ij两点之间边的个数若有权图则用来表示Ij两点之间的距离或者其他权值

第十五页，共五十三页，2022年，8月28日二、邻接表（链式）表示法对每个顶点vi建立一个单链表，把与vi有关联的边（即度或出度边）链接起来，表中每个结点都设为2个域；adjvexnextarc权值datafirstarc表结点头结点邻接点域，表示vi一个邻接点的位置链域，指向vi下一个边或弧的结点数据域，存储顶点vi

的序号链域，指向单链表的第一个结点第十六页，共五十三页，2022年，8月28日邻接表的缺点：邻接表的优点：空间效率高；容易寻找顶点的邻接点；一般用于稀疏图判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。邻接表邻接矩阵存储比较邻接矩阵的优点：判断两顶点间是否有边或弧，可以直接判断速度很快一般用于存储稠密图邻接矩阵的缺点：存储空间大会影响算法的空间效率甚至时间效率第十七页，共五十三页，2022年，8月28日讨论：邻接表与邻接矩阵有什么异同之处？1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。②邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（e<<n2)第十八页，共五十三页，2022年，8月28日图的搜索方法1广度优先搜索2深度优先搜索第十九页，共五十三页，2022年，8月28日一、广度优先遍历(BFS)

有时也叫宽度优先遍历第二十页，共五十三页，2022年，8月28日基本算法由Moore和Lee独立提出给定图G和一个源点s,宽度优先遍历按照从近到远的顺序考虑各条边.算法求出从s到各点的距离宽度优先的过程对结点着色.白色:没有考虑过的点黑色:已经完全考虑过的点灰色:发现过,但没有处理过,是遍历边界依次处理每个灰色结点u,对于邻接边(u,v),把v着成灰色并加入树中,在树中u是v的父亲(parent)或称前驱(predecessor).距离d[v]=d[u]+1整棵树的根为s第二十一页，共五十三页，2022年，8月28日BFS算法BFS(G,s)//从s点开始对图G广度优先搜索foreachvertexu∈V[G]-{s}docolor[u]←white//每个点赋值为未处理d[u]←∞//每个点与源点的距离标志为∞∏[u]←NIL//每个点赋值为没有父亲color[s]←gray//s点标为正在处理d[s]←0//s点与源点的距离为0Q←ф//建空队列保存灰色顶点ENQUEUE(Q,s)//源点入队列While（Q≠ф）dou←DEQUEUE(Q);//从队列中拿出一个元素进行处理foreachv∈Adj[u]//对没有处理过的邻接点进行处理doifcolor[v]=whitethencolor[v]←grayd[v]=d[u]+1∏[v]=uENQUEUE(Q,v)color[u]=black//标记为处理完毕第二十二页，共五十三页，2022年，8月28日第二十三页，共五十三页，2022年，8月28日用BFS求最短路定理:对于无权图(每条边的长度为1),BFS算法计算出的d[i]是从s到i的最短路满足d[i]=1的点一定是正确的(因为长度至少为1),并且其他点都满足d[i]>1.容易证明对于任意距离值x,d[i]=x的点一定是正确的,而且白色点(没有计算出距离的点)的距离一定至少为x+1更进一步,根据每个点的parent值,可以计算出它到s的一条最短路第二十四页，共五十三页，2022年，8月28日Bfs算法中路径的打印Print-Path(G,s,v)if(v==s)thenprintselseif∏[v]=NILthenprint“nopathfrom”s”to”v”exits”elsePrint-path(G,s,∏[v])printv第二十五页，共五十三页，2022年，8月28日机器人问题Dr.Kong是设计了一个可以前进或者后退的机器人，该机器人在每一个位置i会得到一个移动的步数指令Ki（i=1，2···n），聪明的机器人会自己判断是要前进Ki步还是要后退Ki步。例如：给定指令序列（3，3，1，2，5），表示机器人在第一个位置时，可以前进3步到第4个位置，此时后退是不起作用的，出界：机器人在第2个位置时，可以前进3步到第5个位置，此时后退时不起作用的，出界：机器人在第3个位置的时，可以前进1步到第4个位置，也可以后退一步到第2个位置等等.你认为，对于给定的两个位置A，B，聪明的机器人从A位置到B位置至少需要判断几次？input第一行：M表示以下有M组测试数据（0<M<=8）接下来每组有两行数据头一行：NAB（1<=N<=50,1<=A,B<=N）下一行：K1K2···Kn（0<=Ki<=N）output输出有M行，第i行为第i组测试数据的最少判断次数，若无法到达，则输出-1。样例输入25153312585312153111样例输出3-1第二十六页，共五十三页，2022年，8月28日分析发现这道题目就是用宽度优先搜索求最短路径的题目有n个顶点Ki表示i------i+Ki和i-----i-ki之间有通路（当然i+Ki，i-ki为合法顶点）求A----B的最少判断次数就是求A——B的最短路径通广搜可以求出最短路径第二十七页，共五十三页，2022年，8月28日机器人问题boolargs[51][51];intd[51];boolvisited[51];memset(args,false,sizeof(args));memset(d,0xfffff,sizeof(d));memset(visited,false,sizeof(visited));intn,a,b;cin>>n>>a>>b;for(inti=1;i<=n;i++){ inttemp; cin>>temp; if(i+temp<=n)args[i][i+temp]=true; if(i-temp>=1)args[i][i-temp]=true;}

d[a]=0;visited[a]=true;queue<int>q;q.push(a);while(!q.empty()){inttemp=q.front(); q.pop(); for(inti=0;i<=n;i++) { if(args[temp][i]&&!visited[i]) { d[i]=d[temp]+1; visited[i]=true; q.push(i); }}}cout<<d[b]<<endl;第二十八页，共五十三页，2022年，8月28日二、深度优先遍历(DFS)第二十九页，共五十三页，2022年，8月28日深度优先搜索(DFS)基本思想：——仿树的先序遍历过程。Depth_FirstSearchv1v1v2v3v8v7v6v4v5DFS结果例1：→→→→→→→v2v4v8v5v3v6v7例2：v2→v1→v3→v5→DFS结果v4→v6起点起点遍历步骤第三十页，共五十三页，2022年，8月28日深度优先搜索（遍历）步骤：详细归纳：在访问图中某一起始顶点

v

后，由

v出发，访问它的任一邻接顶点

w1；再从

w1出发，访问与

w1邻接但还未被访问过的顶点

w2；然后再从

w2出发，进行类似的访问，…

如此进行下去，直至到达所有的邻接顶点都被访问过的顶点

u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。

如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；

如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。简单归纳：访问起始点v;

若v的第1个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找v的第2个邻接点重新遍历。第三十一页，共五十三页，2022年，8月28日基本算法新发现的结点先扩展得到的可能不是一棵树而是森林,即深度优先森林(Depth-firstforest)特别之处:引入时间戳(timestamp)发现时间d[v]:变灰的时间结束时间f[v]:变黑的时间1<=d[v]<f[v]<=2|V|初始化:time为0,所有点为白色,dfs森林为空对每个白色点u执行一次DFS-VISIT(u)第三十二页，共五十三页，2022年，8月28日DFS-VISIT算法初始化:time为0,所有点为白色,dfs森林为空对每个白色点u执行一次DFS-VISIT(u)时间复杂度为O(n+m)第三十三页，共五十三页，2022年，8月28日第三十四页，共五十三页，2022年，8月28日DFS树的性质括号结构性质对于任意结点对(u,v),考虑区间[d[u],f[u]]和[d[v],f[v]],以下三个性质恰有一个成立:完全分离u的区间完全包含在v的区间内,则在dfs树上u是v的后代v的区间完全包含在u的区间内,则在dfs树上v是u的后代三个条件非常直观第三十五页，共五十三页，2022年，8月28日DFS树的性质定理1(嵌套区间定理):在DFS森林中v是u的后代当且仅当d[u]<d[v]<f[v]<f[u],即区间包含关系.由区间性质立即得到.定理2(白色路径定理):在DFS森林中v是u的后代当且仅当在d[u]时刻(u刚刚被发现),v可以由u出发只经过白色结点到达.证明:由嵌套区间定理可以证明第三十六页，共五十三页，2022年，8月28日非递归形式的深度优先搜索算法voidDFS(GraphG,intv){//非递归算法InitStack(S);visited[]=FALSE;//所有的顶点尚未被访问过Push(S,v);//其实顶点压栈while(!Empty(S)){Pop(S,u);//访问顶点并修改标志数组if(!visited[u]){visit(u),visited[u]=TRUE};for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)){if(!visited[w])Push(G,w)}//将没访问的邻接点压栈}DestroyStack(S);//释放栈}//DFS第三十七页，共五十三页，2022年，8月28日数据结构书上的深度优先搜索算法boolvisited[max];//访问标志数组Status(*VisitFunc)(intv);//函数变量voidDESTraverse(GraphG,status(*visit)(intv)){//对图G进行深度优先搜索（图G连通与否都可以）visitFunc=visit;//使用全局变量Visitfunc，使DFS函数不必设置函数指针//访问标志数组初始化为全部没有访问for(v=0,v<G.vecnum;++v)visitd[v]=false;for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);//对尚未访问的结点进行DFS访问}VoidDFS(GraphG,intv){//从第v个顶点开始递归的深度优先搜索图Gvisited[v]=true;visit(v);//访问第v个顶点并修改标志位for(w=firstAdivex(G,v),w>=0;w=nextAdjvex(G,v,w))if(!visited[w])DFS(G,w);//对v的尚未访问过的邻接点w递归调用DFS}如果是连通图此处的DFS只会被执行一次如果是非连通图此处DFS执行的次数就是连通分支数第三十八页，共五十三页，2022年，8月28日图的连通性问题对于无向图若是连通图则从图中任意顶点出发进行广搜或者深搜便可以访问到图中的任意顶点非连通图则需要多次调用DFS才可全部访问每次DFS可以访问一个连通分量中的所有顶点调用DFS的次数为图的连通分支数另外采用并查集也可以解决这个问题，并且空间效率比较低。最后若能归并成一个几何则说明为连通的，若最后是多个集合则说明是非连通图对于有向图：以后在学习的过程中会做深入的探讨第三十九页，共五十三页，2022年，8月28日

深搜示例：/JudgeOnline/problem?id=2386

题目大意：如左图所示一块矩形地其中‘W’代表的是水‘.’代表的是陆地其中我们认为每个方格和它的八个方向全部是邻接的问其中有多少池塘题目分析访问一次水方格，我们可以将其8个方向的水方格全部访问，这样我们对一个水方格进行深搜就可以将与其之间有路径的所有点全部访问。既是可以访问一个连通分支（也就是一个湖）。搜索的次数就是湖的个数第四十页，共五十三页，2022年，8月28日示例代码：#include<iostream>usingnamespacestd;inta[101][101];//记录矩形方格对应的是水还是陆地intsum,n,m;//sum记录湖的个数n矩形地的行数m矩形地的列数intflag[101][101];//标记每个方格是否已经被访问过//定义的个方向intd[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};//检查xy是否出界boolcheck(intx,inty){ if(x>0&&x<=n&&y>0&&y<=m) return1; return0;}//以一个方格开始深度优先搜索voiddfs(intx,inty){ if(flag[x][y]||!a[x][y])//点已经访问或者是陆地则停止访问 return; flag[x][y]=1;//标记当前结点已经访问 for(inti=0;i<8;i++)//对当前方格的个邻接方格进行深搜 if(check(x+d[i][0],y+d[i][1])) dfs(x+d[i][0],y+d[i][1]);}第四十一页，共五十三页，2022年，8月28日intmain(){ inti,j; charc; while(cin>>n>>m) { memset(flag,0,sizeof(flag));//全部方格标记为没有访问 memset(a,0,sizeof(a));//方格全部标记为陆地 sum=0;//初始化湖的个数为 for(i=1;i<=n;i++) for(j=1;j<=m;j++) { cin>>c; if(c=='W')a[i][j]=1;//是水的方格标记为水 } for(i=1;i<=n;i++) for(j=1;j<=m;j++)//对是水且未被访问过的方格进行深搜 if(a[i][j]&&!flag[i][j])//每次访问访问一个连通分支即一个湖 dfs(i,j),sum++; cout<<sum<<endl; } return0;}对于无向图的连通分支数的判断既可以用广度优先搜索也可以用深度优先搜索大家一定要试着写一下此题的广度优先搜索代码第四十二页，共五十三页，2022年，8月28日推荐题目搜索经典题目迷宫求解：用一个矩形表示地图，其中矩形由方格组成，每个方格为路或者是墙。给你一个起点位置和一个终止位置，问你是否能从开头位置到达终点位置，我们认为起始位置和终点位置是不重合的，并且我们只能走直路，不可以走斜路。我们保证起点和终点都是空位置。要求你求一下这条路径是否存在，存在的话。求出路径的长度输入说明：第一行mn代表矩形是m行n列的pqrs，（p，q）开始位置，（r，s）目标位置接下来的m行每行共n个01代码，其中0代表是通路，1代表是墙。输出说明：有路径输出yes并输出最短路径各一行，没有路径直接输出no占一行示例输入：2200110100示例输出：yes2思路深搜只能求是否有通路，广搜是否有通路和最短路径都可以求出来老队员可以自己在网上搜一些题目做第四十三页，共五十三页，2022年，8月28日拓扑排序问题第四十四页，共五十三页，2022年，8月28日C1

高等数学

C2

程序设计基础

C3

离散数学C1,C2

C4

数据结构C3,C2C5

高级语言程序设计C2C6

编译方法C5,C4C7

操作系统C4,C9C8

普通物理C1C9

计算机原理C8

课程代号课程名称先修课程第四十五页，共五十三页，2022年，8月28日学生课程学习工程图第四十六页，共五十三页，2022年，8月28日检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。第四十七页，共五十三页，2022年，8月28日例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,