图搜索连通性

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2017,年春季,通信网络理论基础,#,50,单击此处编辑母版标题样式,通信网络理论基础,Part 03:,图简介搜索连通性,2017,年春季,通信网络理论基础,2,50,图的概念、搜索、连通性,本课程所涉及的“图”，是一个关于实体,/,对象,/,数据的组织、关联关系的数学,/,抽象概念。既不是“图形”，也不是“图像”。,1,图的基本概念,2,图的搜索算法,3,图的连通性,3,50,Euler Knigsberg,K,nigsberg 7,桥问题,能否找到一条游览路线，使得游客经过所有,7,个桥，要求每个桥只经过,1,次，并且刚好回到起点。,Why is it so important?,Euler1736,年的,工作不仅解决了该问题，且,其解决,方法所,蕴涵的思想开创了一,个方向,：只关注连接关系，而不考虑形状,/,测量等几何性质。,因此，这不仅被,看作图论,的起源，也被看作是拓扑学的第一个结果。,2017,年春季,通信网络理论基础,4,50,基本术语,(,一,),如果图中任意两个顶点之间都邻接，则称该图为全连通图,(full mesh),。,全连通图,顶点,u,和,v,之间有边相连，则称,u,和,v,邻接（,adjacent,）。,邻接,顶点,也称为节点,/,结点,(node),。,边,也称为弧,(arc),，链路,(link),。,边与两个顶点有关,(head,和,tail),。,自环,(loop),如果一条边的头和尾都是同一个顶点，则称为自环。,度,(degree),与顶点相连的边的数目,(,或与之邻接的顶点数目,),。,也称价,(valence),。,可达,两个顶点之间如果存在路径，则称这两个顶点可达,(reachable),。,连通图,如果图中任意两个顶点之间都可达，则称该图为连通,(connected),。,圈,(cycle),如果路径的起点和终点是同一个顶点，称为圈，或回路,(circuit),，环路。,路径,(path),路径由首尾相连的一系列边构成。,起点和终点。,图,(Graph),由顶点,(Vertex),集合和边,(Edge),集合构成。,点间关系,关于路径,关于顶点,关于边,与顶点,u,直接相连的边与,u,关联；反之，,u,也与这些边关联,(Incident),。,关联,关于图,点边关系,2017,年春季,通信网络理论基础,5,50,Ideas of Euler (1736),转化为图,陆地,顶点；,桥,边。,问题：是否存在一个圈，它经过所有的边，但每条边只经过一次？,称为,Euler,圈。,必要条件,顶点度数必为偶数,经过一条边，就意味着“离开”某个点,1,次，且“进入”某个点,1,次。,奇数度意味着这个点进入和离开的次数不等。,如果它是圈的起点,终点不可能是它。,如果它不是圈起点,回不到终点了。,2017,年春季,通信网络理论基础,Eulers Theorem,6,50,充分条件,偶度数连通图，必然存在,Euler,圈。,从任意顶点,w,离开，每经过一个点，随意选择离开的边,(,然后删除,),。直到到达某个顶点，已没有可供离去的边。,Eulers Theorem,连通图中存在,Euler,圈的充要条件是顶点度数全为,偶数。,这个点一定是,w,！,如果图中还有其它边没有经过，一定可以从刚才这个圈中的某个点出发，继续下去。,2017,年春季,通信网络理论基础,Variations(1/3),7,50,Can you modify THE graph, making it include a Euler Cycle?,2017,年春季,通信网络理论基础,Variations(2/3),8,50,IMPOSSIBLE,Theorem:,顶点度数之和必为偶数；且为边数的,2,倍。,Corollary:,奇数度顶点的数目必为偶数。,How about this: there are odd number of vertices whose degree is odd?,2017,年春季,通信网络理论基础,Variations(3/3),9,50,Euler Path,Todays Knigsberg (Kaliningrad) has only 5 bridges,2017,年春季,通信网络理论基础,10,50,基本术语,(,二,),：有向图,/Digraph,有向图,Directed Edge,可用有序顶点对表示，前者表示边的尾,/,起始，后者表示边的头,/,终止。,作图时，用箭头表示有向边的头,/,终止。,有向边,出度,Outdegree,以顶点,v,为起始的有向边数目。称为,v,的出度。,入度,Indegree,以顶点,v,为终止的有向边数目。称为,v,的入度。,0,1,2,3,0,1,2,3,有向圈,有向无圈图,DAG, Directed Acyclic Graph,注意不是树。,2017,年春季,通信网络理论基础,11,50,基本术语,(,三,),：加权图,加权图,加权图中，每条边都赋予了一个或多个权重。,权重可以代表各种物理意义。,也称为网络,(Network),。,Simple Path,不含圈的路径。,简单路径,22,10,16,78,35,6,A,B,C,D,E,22,10,16,2,35,6,A,B,C,D,E,路径权重,加性权重：路径的权重等于路径所经过的所有边的权重之和。,也可能存在其它类型的权重，比如乘性权重，最大最小权重等。,2017,年春季,通信网络理论基础,12,50,基本术语,(,四,),：树,子图,(subgraph),树,(Tree),不包含任何圈的连通图,判决条件,1),边的数目为顶点数目减,1,，且不含圈。,2),边的数目为顶点数目减,1,，且连通。,3),任意两顶点间存在唯一路径。,4),删除任意一条边，图就不连通了。,生成树,如果图,G,的一个子图包含了,G,的全部顶点，且为树，则称之为,G,的生成树,(Spanning Tree),2017,年春季,通信网络理论基础,13,50,图的表达方法,每条边都拥有一个链表，记录与之关联的节点。,n,行,m,列矩阵,i,行,j,列为,1,，表示第,i,个节点与第,j,条边关联。,n,行,n,列矩阵,i,行,j,列为,1,，表示节点,i,与节点,j,邻接。,n,行,n,列矩阵,i,行,j,列的元素值表示节点,i,到,j,的最小距离（跳数）。,可通过邻接矩阵自乘得到。,Kirchhoff matrix,邻接矩阵的对角线上填写节点的度数。,邻接链表,关联矩阵,邻接矩阵,拉氏矩阵,距离矩阵,关联链表,每个节点都拥有一个链表，记录与之邻接的其它节点。,一般地，我们用,n,表示图中节点的数目，用,m,表示图中边的数目,。即,，给定图,G(V, E),，,n = | V |, m = | E |,2017,年春季,通信网络理论基础,14,50,Adjacency Matrix,0,1,2,3,0,1,2,3,4,有向图,无向图,对称矩阵,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,2017,年春季,通信网络理论基础,15,50,Adjacency List,0,1,2,3,4,有关邻接点的信息,指向下一个邻接点的指针,2,3,4,0,0,1,0,0,2,3,4,1,4,1,3,链表元素,指针数组,2017,年春季,通信网络理论基础,邻接链表的建议,20,17,年春季,通信网络理论基础,16,50,多数图算法都需要方便地访问,/,扫描,给定顶点的邻接点或者关联边。,WHY,？,本课程推荐使用邻接链表。,占用空间较少。,邻接矩阵的空间？,邻接链表的空间？,很多有价值的应用场景中，都是大规模的稀疏图。,n,vs,m,20,17,年春季,通信网络理论基础,17,50,假定图,G,(,V,E,),具有,n,个顶点，,m,条边。,【,一般我们都假定是,没有平行边和自环的所谓“简单图”,】,如果,G,是无向图，,m,和,n,什么关系？,如果,G,是有向图呢？,如果要求,G,是连通的，,m,和,n,什么关系？,邻接链表的实现,20,17,年春季,通信网络理论基础,18,50,第一种实现：,指针数组,，每个元素都指向一个链表,【,Adj,i,指向节点,i,的所有邻接点构成的链表。,】,第二种实现：,双数组实现,。,顶点数组,V,，边数组,E,。,每个边都含有指向其端点的指针。,每个顶点都含有指向,其关联边,的指针。,第三种实现：,面向对象实现,。,v.Neighbors,=,Adjv,第四种实现：,隐式实现,。,将,Adj(u),实现为一个函数；,v.neighbors(),实现为方法。,图太大，但相对规则时很有优势,“零空间”。,2017,年春季,通信网络理论基础,19,50,图的概念、搜索、连通性,图搜索看起来并未解决什么重要的问题，但却是很多图算法的基础。而且其中“搜索”的概念和方法还可以扩展到更广阔的应用空间。,1,图的基本概念,2,图的搜索算法,3,图的连通性,图搜索的目标和模式,2017,年春季,通信网络理论基础,20,50,图搜索的目标：给定一个,起点,，,探索,完图中所有顶点。,要求：每个点只探索一次。,需要一个布尔变量来记录某个顶点是否被探索过。,要求探索完所有顶点的问题，有时也称为“遍历”。,基本模式：“边界扩展”,每个中间步骤开始时，顶点分为,两个集合；已探索,vs.,未探索,从“边界”上,挑选,一个点去探索,直至所有顶点都被探索为止,已探索集合,未探索集合,边界点,图搜索的应用,20,17,年春季,通信网络理论基础,21,50,除了我们后面会讲到的一些应用之外。还有：,Web,Crawling(,how,Google,finds,pages),Social,Networking(,Facebook,friend,finder),Network,broadcast,routing,Garbage,Collection,Model,Checking(FSM),Checking,mathematical,conjectures,Solving,puzzles,and,games,BFS,&,DFS,20,17,年春季,通信网络理论基础,22,50,BFS,（,Breadth,First,Searching,），广度优先搜索，广搜,从边界点中，优先选择对拓展广度有帮助的点。,类似“扫描”。,“层”的概念。,DFS,（,Depth,First,Searching,），深度优先搜索，深搜,从边界点中，优先选择对拓展深度有帮助的点。,类似“走迷宫”。,“回溯”的概念：走不通了才会回退。,课堂练习：写出,BFS,和,DFS,的伪码。,循环不变式,20,17,年春季,通信网络理论基础,23,50,概念：每次循环开始时都要保持的性质,/,状态。,【,既是证明正确性的基础，也是设计循环的思路,】,为了保证图搜索,(,边界扩展,),的正确，应该保证什么性质？,INVARIANT,已探索集合和未探索集合应该处于正确的状态。边界点集合应准备好了。,循环开始时，从边界点集合中选择一个顶点进行探索。,循环结束前，将新扩展的边界点纳入集合。,注意：,BFS,和,DFS,选择边界点的策略不同。,BFS,用队列,(FIFO),；,DFS,用堆栈,(LIFO),。,维护边界点集合的方式如何影响选择策略？,图搜索伪码,20,17,年春季,通信网络理论基础,24,50,BFS(,G, s,),/,B=,所有边界点构成的集合,B.EnQueue(s);,WHILE B,非空,d=B.DeQueue();,将,d,标记为“已探索”；,FOR d,的所有邻居,t,IF,t,的标记为“未探索”,B.EnQueue(t);,ENDFOR,ENDWHILE,DFS(,G, s,),/,B=,所有边界点构成的集合,B.Push(s);,WHILE B,非空,d=B.Pop();,将,d,标记为“已探索”；,FOR d,的所有邻居,t,IF,t,的标记为“未探索”,B.Push(t);,ENDFOR,ENDWHILE,课堂练习：,DFS,的递归版本。,课堂练习：,BFS,的运行时间分析。,复杂度分析,20,17,年春季,通信网络理论基础,25,50,BFS(,G, s,),/,B=,所有边界点构成的集合,B.EnQueue(s);,WHILE B,非空,d=B.DeQueue();,将,d,标记为“已探索”；,FOR d,的所有邻居,t,IF,t,的标记为“未探索”,B.EnQueue(t);,ENDFOR,ENDWHILE,Naive,分析的要点,以循环为重点。,循环次数按照最坏情况估计。,循环内的操作次数也按最坏,情况估计。,二者相乘即作为分析结果。,BFS,的,Naive,分析结果？,O(,nm,),什么地方不太对吧？,最坏情况的确是一次循环中检查,m,条边。,但在那种实例下，其他循环岂不是根本不用检查了？,聚合分析,20,17,年春季,通信网络理论基础,26,50,BFS(,G, s,),/,B=,所有边界点构成的集合,B.EnQueue(s);,WHILE B,非空,d=B.DeQueue();,将,d,标记为“已探索”；,FOR d,的所有邻居,t,IF,t,的标记为“未探索”,B.EnQueue(t);,ENDFOR,ENDWHILE,聚合分析的要点,以数据结构为核心。,将整个程序看作一个总体。,考察数据结构的操作次数。,总的入队次数是多少？,n,次,每条边会被检查几次？,总的出队次数是多少？,n,次,无向图：,2,次；有向图：,1,次,Total,？,O(,n,+,m,),DFS,呢？,也是,O(,n,+,m,),图搜索算法,(DFS/BFS),都是线性时间的算法。,BFS,的应用,20,17,年春季,通信网络理论基础,27,50,BFS,的应用,求最短路。,判断一个给定的图是否偶图。,最短：跳数最少；层数就是跳数；证明参见教材。,偶图,如果图的顶点可以划分为两个集合，使得任一集合内部的任意两个顶点都不邻接，则称该图为偶图,(Bipartite),课堂练习：构造算法判断一个给定的无向图是否偶图。,DFS,的应用,20,17,年春季,通信网络理论基础,28,50,DFS,的应用,拓扑排序。,求两点间所有的简单路径。,有向无环图；参见教材。,利用堆栈的特性。,PROJECT #1,：设计并实现求两点间所有路径的算法。,更宽广的视野,20,17,年春季,通信网络理论基础,29,50,如果将待求解问题的所有可能的解建模为图。,顶点：可行解。,边：解之间的变换关系。,图搜索的过程，就是在寻找特定解的过程。,BFS,分支定界法。,定义合适的裁剪分支的策略。,DFS,回溯法。,定义合适的判定最佳的策略。,分支定界和回溯被看作是两种求解问题的基本范型。,2017,年春季,通信网络理论基础,30,50,图的概念、搜索、连通性,求出给定图的连通部分属于那种“乍一看容易，其实不然”的问题。这些算法不仅是图搜索的应用，本身,也是“原语”性质的算法。,1,图的基本概念,2,图的搜索算法,3,图的连通性,无向图的连通分量,20,17,年春季,通信网络理论基础,31,50,含义：“,pieces,of,a,undirected graph”,7,9,5,1,3,4,2,8,10,6,定义,关系,集合,A,中的关系定义为,A,与其自身的笛卡尔积。,等价关系,同时满足自反、对称、传递性质的关系称为等价关系。,等价类,满足等价关系的元素构成的集合。,自反？,CHECK,对称？,CHECK,传递？,CHECK,BFS,求无向连通分量,20,17,年春季,通信网络理论基础,32,50,随便选个起点，调用,BFS,，可以探索到所有图中顶点吗？,BFS/DFS,can explore,every,vertex,reachable,But,nothing more,.,那怎么办？,选个没探索过的再次调用,BFS,就是了。,Loop-BFS( G,),FOR i=1 to n,IF,i,的标记为“未探索”,BFS(G, i);,ENDFOR,Naive,分析？,聚合分析？,7,9,5,1,3,4,2,8,10,6,有向图的强连通分量,20,17,年春季,通信网络理论基础,33,50,我们说有向图是“连通的”，是什么意思？,定义,左图没有“散成几块”。,但某些点却“到不了”某些点。,这个图是“弱连通”的。,但不是“强连通”的。,请问上图有几个强连通分量（,Strongly Connected,Component,SCC,）,?,对比无向图的连通分量,4,个。,TWO-PASS,算法,20,17,年春季,通信网络理论基础,34,50,TWO-PASS,算法（,Kosaraju,算法）,将原图,G,中的每条边都反向，得到,G,rev,在,G,rev,中运行,Loop-DFS,，记录每个顶点的,完成时间,f,(,v,).,按,f,(,v,),的降序,，,在,G,中运行,Loop-DFS,，记录每个顶点的,Leader,l,(,v,).,具有相同,leader,的顶点属于同一个,SCC,。,Loop-DFS( G,),全局变量,t=0,全局变量,s=NULL,/,假定顶点从,1,到,n,排序,FOR i=1 to n,IF,i,的标记为“未探索”,s = i;,DFS(G, i);,ENDFOR,DFS( G, i,),将顶点,i,设置为“已探索”,Leader(i) = s,FOR i,的所有邻居,j,IF,j,的标记为“未探索”,DFS(G, j);,t+,；,f(i) = t;,ENDFOR,三点注释,(1/3),20,17,年春季,通信网络理论基础,35,50,Loop-DFS( G,),全局变量,t=0,全局变量,s=NULL,/,假定顶点从,1,到,n,排序,FOR i=1 to n,IF,i,的标记为“未探索”,s = i;,DFS(G, i);,ENDFOR,DFS( G, i,),将顶点,i,设置为“已探索”,Leader(i) = s,FOR i,的所有邻居,j,IF,j,的标记为“未探索”,DFS(G, j);,t+,；,f(i) = t;,ENDFOR,顶点的排序,第一次针对,G,rev,调用时，顶点,的编号是任意的,【,未排序,】,。,Leader,的含义,完成时间的含义,第二次针对,G,调用时，顶点的,编号按照完成时间降序排列。,两次调用中顶点排序不同,三点注释,(2/3),20,17,年春季,通信网络理论基础,36,50,Loop-DFS( G,),全局变量,t=0,全局变量,s=NULL,/,假定顶点从,1,到,n,排序,FOR i=1 to n,IF,i,的标记为“未探索”,s = i;,DFS(G, i);,ENDFOR,DFS( G, i,),将顶点,i,设置为“已探索”,Leader(i) = s,FOR i,的所有邻居,j,IF,j,的标记为“未探索”,DFS(G, j);,t+,；,f(i) = t;,ENDFOR,顶点的排序,递归调用,DFS,时，除了最外层，,从,不改变,s,的值。,DFS(G, i),仅在从,i,可达的所有顶,均被探索后才会返回。,Leader,的含义,完成时间的含义,但每次某个顶点被探索时，其,Leader,都会被设置为,s,。,从,i,可达的顶点具有相同的,Leader,。,两次调用中顶点排序不同,三点注释,(3/3),20,17,年春季,通信网络理论基础,37,50,Loop-DFS( G,),全局变量,t=0,全局变量,s=NULL,/,假定顶点从,1,到,n,排序,FOR i=1 to n,IF,i,的标记为“未探索”,s = i;,DFS(G, i);,ENDFOR,DFS( G, i,),将顶点,i,设置为“已探索”,Leader(i) = s,FOR i,的所有邻居,j,IF,j,的标记为“未探索”,DFS(G, j);,t+,；,f(i) = t;,ENDFOR,顶点的排序,Leader,的含义,完成时间的含义,从,i,可达的顶点具有相同的,Leader,。,DFS(G, j),仅在从,j,可达的所有顶,均被探索后才会返回。,FOR,循环保证,i,的所有邻居及其,可达顶点均被探索后才会结束。,仅在从,i,开始的深搜过程完成，,必须回溯时，才会记录其完成。,两次调用中顶点排序不同,EXAMPLE: 1st Pass,20,17,年春季,通信网络理论基础,38,50,7,9,5,1,3,4,2,6,8,假定下图为原图反向后得到的,G,rev,。,1,47(4)285(8)(2)(4)(1),Loop-DFS( G,),全局变量,t=0,全局变量,s=NULL,/,假定顶点从,1,到,n,排序,FOR i=1 to n,IF,i,的标记为“未探索”,s = i;,DFS(G, i);,ENDFOR,DFS( G, i,),将顶点,i,设置为“已探索”,Leader(i) = s,FOR i,的所有邻居,j,IF,j,的标记为“未探索”,DFS(G, j);,t+,；,f(i) = t;,ENDFOR,f(7)=1,f(5)=2,f(8)=3,f(2)=4,f(4)=5,f(1)=6,3,69(6)(3),f(9)=7,f(6)=8,f(3)=9,1,428,5,(8)(2)(4)7(4)(1),f(5)=1,f(8)=2,f(2)=3,f(7)=4,f(4)=5,f(1)=6,3,69(6)(3),f(9)=7,f(6)=8,f(3)=9,EXAMPLE: 2nd Pass,20,17,年春季,通信网络理论基础,39,50,1,7,2,6,9,5,4,8,3,按照,f,值重新编号，并反向。,9,78(7)(9),Loop-DFS( G,),全局变量,t=0,全局变量,s=NULL,/,假定顶点从,1,到,n,排序,FOR i=1 to n,IF,i,的标记为“未探索”,s = i;,DFS(G, i);,ENDFOR,DFS( G, i,),将顶点,i,设置为“已探索”,Leader(i) = s,FOR i,的所有邻居,j,IF,j,的标记为“未探索”,DFS(G, j);,t+,；,f(i) = t;,ENDFOR,Leader =9,615(1)(6),Leader=6,423(2)(4),Leader=4,有人发现了,1st,pass,的作用吗,?,正确的,DFS,调用起点。,接下来的任务,20,17,年春季,通信网络理论基础,40,50,Theorem,任给有向图,G,，,Two-Pass,算法可以在,O(,n,+,m,),时间内计算出所有的,SCC,。,我们接下来的任务就是证明这个定理。,Running,Time,Observation,Key,Lemma,Corollary,Correctness,Intuition,Proof,of Key Lemma,这个最简单,很有用的一个直觉,正确性证明的关键,一个显而易见的推论,不严格，但足以让你明白,最后回过头来证明那个引理。,复杂度分析,20,17,年春季,通信网络理论基础,41,50,聚合分析,对图反向：,O(,m,),第一遍,Loop-DFS,：,O(,n,+,m,),第二遍,Loop-DFS,：,O(,n,+,m,),不是还要对顶点按照完成时间排序吗？,不需要。第一遍,Loop-DFS,的过程中每记录一个,顶点的完成时间，就以,f,为下标放入一个数组。,总计为,O(,n,+,m,),，线性时间！,有用的洞察,20,17,年春季,通信网络理论基础,42,50,Observation,1,7,2,6,9,5,4,8,3,C1,C2,C3,C4,C3,C2,C1,为啥无环？,多个成环的,SCCs,会坍缩成一个,SCC,。,关键引理,20,17,年春季,通信网络理论基础,43,50,Key,Lemma,i,j,7,9,5,1,3,4,2,6,8,f(7)=1,f(5)=2,f(8)=3,f(2)=4,f(4)=5,f(1)=6,，,f(9)=7,f(6)=8,f(3)=,9,f(5)=1,f(8)=2,f(2)=3,f(7)=4,f(4)=5,f(1)=6,f(9)=7,f(6)=8,f(3)=,9,不妨用我们做的例子来验证一下。,一个额外的事实：,G,和,G,rev,的,SCC,是一样的。,例如：令,fi,表示,Ci,中最大的,f,值，则有：,f1f2,f2f4,f1f3,f3f4,。,简单的推论,20,17,年春季,通信网络理论基础,44,50,Key,Lemma,i,j,推论,最大的,f,值必然在,“,sink,”,SCC,中。,注意：有向无环图,必有,sink,。,C4,C3,C2,C1,直觉性“证明”,20,17,年春季,通信网络理论基础,45,50,第二次调用,Loop-DFS,是从一个,sink,SCC (,C,*),中的,某个顶点开始的。,这个首次深搜过程会探索到,C,*中的所有顶点，,却也只能探索到这些顶点。,下一次深搜过程会,从与,C,*“反向邻接”,的某,个,SCC,开始，探索完它，,nothing,more,。,后面的深搜过程不过是逐个“剥离”,meta-,graph,中的,SCC,。,QED,C4,C3,C2,C1,sink,关键引理的证明,20,17,年春季,通信网络理论基础,46,50,Key Lemma,i,j,i,j,在,G,rev,中：,QED,SCC,的应用：,Web,结构,20,17,年春季,通信网络理论基础,47,50,Web,图：网页和超链接分别对应于顶点和边。,Broder,等人,2000,年左右发表文章,：,计算了,web,图中,SCC,。,图,(2,亿点,10,亿边,),太大了。在没有,MapReduce/Hadoop,这类工具的当年，需要非常考究的工程优化技巧。,主要发现,四大部分的规模差不多,核心内部不仅强连通，而且路径极短。（小世界）,除核心外的部分：连通性出人意料地差。,CORE,:,Giant,SCC,Bowtie,结构,小结（,1/3,）,20,17,年春季,通信网络理论基础,48,50,图简介,图搜索,连通性,主要内容,图的基本概念和术语,图的表达与存储,在实验中熟悉图的概念。,小结（,2,/3,）,20,17,年春季,通信网络理论基础,49,50,图简介,图搜索,连通性,主要内容,BFS,和,DFS,边界扩展模式,循环不变式：从思路到伪码,别忘了你们的第一个,PROJECT,。,聚合分析,小结（,3/3,）,20,17,年春季,通信网络理论基础,50,50,图简介,图搜索,连通性,主要内容,无向图的连通分量：,BFS,有向图的强连通分量：,Two-Pass,请体会：证明不仅是“说服”，更是“理解”。,正确性证明,