ACM暑期培训课程--图论2

《ACM暑期培训课程--图论2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ACM暑期培训课程图论基础算法（二）03061396王玉操提纲图的连通性E问题H问题二部图匹配图的连通性什么是连通性？所谓连通性，直观的讲，就是“连成一片”。什么叫“连成一片”啊？看一个例子：如右图G1，你认为它是连通的吗？那么右图G2呢？G2不连通连通图的连通性什么是连通性？无向图G中，如果任意两顶点u和v，都能找到从一条u到v的路径。称无向图G是连通的。当G为有向图时，若G中存在一条以u为起点v为终点的有向路P，则称从u到v是可达的。如果G的任何两个顶点都是相互可达的，则称图G是强连通的；如果G的有向边被看作无向边时是连通的，则称有向图G是弱连通的。现在看图G1，我们发现，按照上面

2、的划分方法，我们可以把G1分为三部分，如右图：因此，G1是不连通的，但是，这三个部分，我们把它们叫做图G1的三个连通分量。图的连通性什么是连通性？所谓连通分量，指的是图中的极大连通子图。有了连通分量的概念，我们可以对图的连通性换言之为：如果图G中只有唯一一个连通分量，那么G是连通的，我们称G为连通图。强连通弱连通弱连通G1G2G3问：下面三个图中，哪些是强连通图，哪些是弱连通图？图的连通性2.无向图的连通性判定在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先遍历或广度优先遍历，便可访问到图中所有顶点；对于非连通图，则需从多个顶点出发进行遍历，而每次从一个新的起点出

3、发进行遍历得到的顶点访问序列恰好是一个连通分量中的顶点集。对无向图的连通性判定，一般我们采用搜索的方法，这里我们首先要提到应用非常广泛的深度优先搜索算法DFS，DFS在图论算法中有非常重要的地位。对于DFS算法思想的本身我不做介绍，前面的大牛们已经讲过了，所以，我们直接应用此算法来探讨无向图的连通性判定思想。图的连通性2.无向图的连通性判定对下图(a)所示无向图进行深度优先遍历，需分别从顶点v1和v5出发调用两次DFSTravers（或BFSTravers），得到的顶点序列分别为：v1v2v3v4和v5v6。这两个顶点集分别加上所有依附于这些顶点的边，便构成了非连通图G的两个连通分量，

4、如下图(b)所示。(a)非连通图G(b)G的两个连通分量图的连通性2.无向图的连通性判定因此，要想判定一个无向图是否为连通图，或有几个连通分量，可以设置一个计数器count，初始时取值为0，每调用一次遍历算法，就给count增1。这样，当整个遍历算法结束时，依据count的值，就可确定图的连通性了。算法用伪代码描述如下：查看源代码图的连通性2.无向图的连通性判定源代码无向图连通分支//无向图连通分支，dfs邻接阵形式，o（n^2）//返回分支数，id返回1..分支数的值//传入图的大小n和邻接阵mat，不相邻点边权0#defineMAXN100voidfloodfill(intn,i

5、ntmat[][MAXN],int*id,intnow,inttag){inti;for(id[now]=tag,i=0;i

6、性3.有向图的连通性判定其实，在讲完无向图的连通性判定时，基本上就等于也讲了有向图的连通性判定了，为什么呢？假设，我们把一张有向图的所有边看做无向的，然后对转化后的无向图进行一次DFS，是不是就可以判断无向图的连通性呢？显然可以。这里，我只讲讲思路：对于采用邻接矩阵表示的有向图G=，如果存在一条边e(u,v),那么在矩阵中e(u,v)>0，我们令e(v,u)=e(u,v)，这样就可以将一条有向边变成无向边。之后，对于这个转化后的矩阵进行一次DFS，这样既可以判断有向图是否连通。需要注意的是，一般情况下，我们在题目中应用到得不是简单的有向图是否连通，而是：求有向图的强连通分量。

7、图的连通性4.有向图的强连通分支(StronglyConnectedComponents)什么是强连通分支？有向图G的极大强连通子图称为G的强连通分支(SCC)。如何求有向图的强连通分支？深度优先遍历仍然是求有向图的强连通分支的一个有效方法，具体求解步骤如下：(1)对G执行深度优先搜索，求出每个顶点的后序遍历顺序号postOrder。(2)反转有向图G中的边，构造一个新的有向图G*。(3)由最高的postOrder编号开始，对G*执行深度优先搜