wordpress内容付费,常德百竞seo,百度工具seo,深圳松岗做网站的1. 连通性
什么是连通性#xff1f;
连通#xff0c;字面而言#xff0c;类似于自来水管道中的水流#xff0c;如果水能从某一个地点畅通流到另一个地点#xff0c;说明两点之间是连通的。也说明水管具有连通性#xff0c;图中即如此。
无向图和有向图的连通概念稍有差…1. 连通性
什么是连通性
连通字面而言类似于自来水管道中的水流如果水能从某一个地点畅通流到另一个地点说明两点之间是连通的。也说明水管具有连通性图中即如此。
无向图和有向图的连通概念稍有差异。
无向图连通性
如果任意两点间存在路径称此图具有连通性如下的图结构具有连通性。提及连通性就不得不说连通分量通俗而言指结构中有多少个连通通道如下的图结构只有一个连通通道也就是一个连通分量所有节点在这个连通通道上都能互通。 而下图则有2个连通分量。1,2,3,4,5可以在一个连通通道上互通不能和6,7互通。6,7在自己的连通通道上可以互通。 如何检查图结构的连通性和计算连通分量
笨拙的方案自是使用深度或广度搜索算法。原理较简单一次搜索完毕后搜索到的节点必是在一个连通分量上。如果一次搜索完毕后被搜索出来的节点数量和图结构原有的节点数量相同可证明只有一个连通分量。否则可以再次从除第一次搜索出来的节点之外的节点开始重新搜索再检查搜索出来的节点数量……如此如此便可以检测出所有连通分量。
在性能要求不高的应用场景这是不错的选择。否则可以使用轻巧、快速的并查集数据结构来检查。
有向图的连通性
无论是在有向图或无向图中都不可能改变连通这个概念。区别于有向图中的边有方向无向图中的连通可以认为是双向通道可认为是广义连通有向图中的连通则是单向通道可认为是狭义连通。
有向图中如果一个节点能通过单向通道到达另一个节点可认为这两点之间是连通的。如下图中4-1、2-4-1是连通的而2-3是不连通的。讨论连通的局部性没有太大意义有向图中讨论的是强连通性。 什么强连通
强连通是有向图的特定概念。有向图中任意两点之间都可以连通则认定此有向图为强连通图如下图。 连通分量用来记录连通通道的数量有向图中的连通分量指强连通分量。如上图有一个强连通分量也称此图为强连通性有向图。
如下图所示有向图结构有向图本身不具有强连通性但存在子图具有强连通性则称子图即为原图的强连通分量。 当然具有强连通性的子图可能不只一个。猜一猜下图有几个连通分量。 我们已知在无向图中计算连通分量的算法。那么在有向图中如何计算机强连通分量
算法界有一句名言没有暴力算法不能解决的问题。有向图中查找强连通子量同样可以使用深度搜索或广度搜索。可以说在树和图论问题中没有广度和深度搜索算法解决不了的。说起来感觉很历害道理却是简单任何问题都是在能搜索到的前提下得到解决的。
直接使用广度或深度搜索毫无疑问属于暴力算法。虽然这是一条康庄大道但是不一定是一条捷径之路。好吧现在让我们去发现是否有捷径小道。
2. Tarjan算法
Tarjan算法很优秀也很优雅颇有风淡云轻四两拨千金之感。理解Tarjan算法先要知晓几个概念如DFS序、时间戳、回溯值……这些可以查阅我的文章《DFS序和欧拉序的降维打击》。
Tarjan可以解决很多问题。如公共祖先、割点、割边……当然还有本文的强连通分量的求解。
理解Tarjan算法求解强连通分量的工作机制之前先搞明白有向图的 DFS 生成树中的 4 种边。
树边(tree edge)节点与节点之间的边。反祖边(back edge)上图中以红色边表示即 7-1)也被叫做回边即指向祖先节点的边。横叉边(cross edge)上图中以蓝色边表示即 9-7 )搜索的时候遇到的一个已经访问过的结点但是这个结点 并不是 当前结点的祖先。前向边(forward edge)上图中以绿色边表示即 3-6)在搜索的时候遇到子树中的结点的时候形成的。搜索过程所有前向边组成一条搜索分支。
DFS生成树与强连通分量之间的关系
如果结点 u 是某个强连通分量在搜索树中遇到的第一个结点那么这个强连通分量的其余结点肯定是在搜索树中以 u为根的子树中。结点 u被称为这个强连通分量的根。
以下图的结构为例讲解查找强连通分量的流程。 准备变量
栈sta存储强连通分量上的所有节点dfn记录节点的时间戳一个结点的子树内结点的 dfn 都大于该结点的 dfn。也可以记录节点是否被访问过。low(回溯值)记录节点通过一条不在搜索树上的边能到达的结点。或者说不经过直接父节点能访问到的最早远的祖先或者说是经过回边访问到的祖先节点。
搜索过程
从节点1开始深度搜索记录每一个节点在DFS时的时间戳以及回溯值。如1号节点的刚开始的时间戳为1回溯值为1。别忘记了1号节点现在也在栈中。 按深度搜索路线一路下去后面应该是2、5、4。下图给出了当搜索到4号节点时每一个节点的时间戳和回溯值以及栈中的状态。此时栈中由栈底到栈顶存储着一条DFS搜索树1-2-5-4。 当从4号节点访问到2号节点时转机出现了。因为2节点被访问过现又以4号节点的子节点身份重新被访问会想到是不是碰到了祖先或者说遇到了同一个强连通分量上的节点 答案是不能这么简单的认为因为这种情况有可能是回边也有可能是横叉边。 如下图所示。 从1号开始深度搜索在第一条深度搜索分支结束后4号节点也会被标记为被访问过。回溯到1号节点后会开始第二条分支在再次搜索到4号节点时同样会发现4号节点也被访问。难道说4号节点和1号节点在同一个强连通分量上吗4-2是回边而1-4是横叉边。 那么应该如何做出正确判断继续回到我们的图结构上来讨论怎么正确得到强连通分量。
下图中2号节点在栈中说明早于4号节点被访问到且还没有加入其它的强连通分量上可以判断2是4号的祖先。所以节点是否在栈中是判断是不是回边的一个很重要的条件。 于是更新4号节点的low[4]2。既然4号节点能到达2号节点显然点4的父节点们也能通过4号节点到达2号节点……一脉相承吗于是这些节点的low值得以更新。 4号节点除了2号节点外没有其它子节点搜索结束回溯到4号因其dfs[4]!low[4]暂时不要出栈继续回溯到5号节点因为dfs[5]!low[5]不出栈。继续回溯到2号节点因其dfs[2]low[2]说明一个强连通分量到2号节点结束。把它们从栈中弹出来得到第一个强连通分量上的所有节点。 **Tips**如果 i 节点的dfn[i]!low[i]说明其节点可以回到更早的祖先。也说明其在以祖先开始的强连通分量上。所以只有一直回溯到祖先时才能一一出栈。Tarjan算法求解强连通分量中栈起到了至关重要的作用。 一旦发现一个强连通分量就会把这个强连通分量上的节点弹出来。所以访问过、但是不在栈中的节点说明已经加入到了另一个强连通分量上。如果访问过但是还在栈中的节点说明还没有找到归属。 回溯到1号节点时因dfn[1]low[1]。1号节点构成只有一个节点的强连通分量。
小结
**深度搜索阶段**如果 u节点的子节点v已经访问、且在栈中。说明v是u的祖先更新u的low值。同时更新u的除了v之外祖先的low值。**回溯阶段**如果u节点的dfn!low继续向上回溯 如果u节点的dfnlow说明找到了一个强连通分量把栈中u节点包含 u之上的节点全部弹出来。
编码实现
#includeiostream
#includestack
#includevector
using namespace std;
//节点数、边数
int n,m;
//dfn记数器和强连通分量记数器
int cnt,cntb;
//矩阵存储图
vectorint edge[101];
//记录强连通分量
vectorint connections[101];
//是否在栈中
bool inSta[101];
//时间戳
int dfn[101];
//回溯值
int low[101];
//栈
stackint s;void getConn(int u) {cnt;//前序位置记录节点的时间戳和回溯值dfn[u]low[u]cnt;//入栈s.push(u);inSta[u]true;//遍历子节点for(int i0; iedge[u].size(); i) {int vedge[u][i];if(!dfn[v]) {//没有被访问getConn(v);//回溯位置根据子节点的 low 更新父节点的 lovwlow[u]min(low[u],low[v]);} else if(inSta[v])//访问过且在栈中遇到了回边。更新 low 为祖先节点的时间戳low[u]min(low[u],dfn[v]);}//后序遍历位置if(dfn[u]low[u]) {//如果时间戳和回溯值相同找到一条强连通分量cntb;int t;do {ts.top();s.pop();inSta[t]false;connections[cntb].push_back(t);} while(t!u);}
}
int main() {cinnm;for(int i1; im; i) {int u,v;cinuv;edge[u].push_back(v);}getConn(1);for(int i1; icntb; i) {coutconn i : ;for(int j0; jconnections[i].size(); j)coutconnections[i][j] ;coutendl;}return 0;
}
//测试数据
//7 11
//1 2
//2 3
//2 5
//2 4
//3 5
//3 7
//7 5
//5 6
//6 7
//4 1
//4 5思考一下如下图的强连通分量有几个。 答案有两个分别是
6 5 4 3 21
3. 总结
强连通分量算法还有Kosaraju 、Garbow 算法。有兴趣者可自行了解。
