选择特殊符号

选择搜索类型

热门搜索

首页 > 百科 > 建设工程百科

强连通分量

有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量(strongly connected components)。

强连通分量基本信息

强连通分量Tarjan算法思路

这个算法思路不难理解,由开篇第一句话可知,任何一个强连通分量,必定是对原图的深度优先搜索树的子树。那么其实,我们只要确定每个强连通分量的子树的根,然后根据这些根从树的最低层开始,一个一个的拿出强连通分量即可。那么剩下的问题就只剩下如何确定强连通分量的根和如何从最低层开始拿出强连通分量了。

那么如何确定强连通分量的根,在这里我们维护两个数组,一个是indx[1..n],一个是mlik[1..n],其中indx[i]表示顶点i开始访问时间,mlik[i]为与顶点i邻接的顶点未删除顶点j的mlik[j]和mlik[i]的最小值(mlik[i]初始化为indx[i])。这样,在一次深搜的回溯过程中,如果发现mlik[i]==indx[i]那么,当前顶点就是一个强连通分量的根,为什么呢?因为如果它不是强连通分量的根,那么它一定是属于另一个强连通分量,而且它的根是当前顶点的祖宗,那么存在包含当前顶点的到其祖宗的回路,可知mlik[i]一定被更改为一个比indx[i]更小的值。

至于如何拿出强连通分量,这个其实很简单,如果当前节点为一个强连通分量的根,那么它的强连通分量一定是以该根为根节点的(剩下节点)子树。在深度优先遍历的时候维护一个堆栈,每次访问一个新节点,就压入堆栈。现 在知道如何拿出了强连通分量了吧?是的,因为当前节点是这个强连通分量中最先被压入堆栈的,那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。当然有人会问真的吗?假设一个节点在当前节点压入堆栈以后压入并且还存在,同时它不属于该强连通分量,那么它一定属于另一个强连通分量,但当前节点是它的根的祖宗,那么这个强连通分量应该在此之前已经被拿出。现 在没有疑问了吧,那么算法介绍就完了。

实现代码(pascal)

由于不同人编辑而注明,代码中数组dfn为上述indx,low为mlik

实现代码(C++)

查看详情

强连通分量造价信息

  • 市场价
  • 信息价
  • 询价

连通

  • PH-123E Q=8.1m3/h H=3.0m P=265w(含变频控制柜)
  • LG
  • 13%
  • 东莞市皇之冠环保热能设备有限公司
  • 2022-12-06
查看价格

连通口封堵

  • FMDB5525(6)
  • 13%
  • 四川特安人防工程设备有限公司
  • 2022-12-06
查看价格

连通

  • PH-123E Q=8.1m3/h H=3.0m P=265w
  • 威乐
  • 13%
  • 东莞市星源环保热能设备有限公司
  • 2022-12-06
查看价格

VGA转分量信号线

  • TS-9005AV VGA转分量信号线
  • ITC
  • 13%
  • 广州保伦电子科技有限公司
  • 2022-12-06
查看价格

电子分量开关

  • 品种:电子分量开关;包装规格(只/盒/箱):60/6/1;规格型号:G08D114;系列:G08系列开关插座;工作电压(V):220;额定电
  • 公牛
  • 13%
  • 北京利丰泰隆商贸有限公司
  • 2022-12-06
查看价格

全自动磁过滤器

  • SNYQ(U) DN50W-1
  • 珠海市2016年6月信息价
  • 建筑工程
查看价格

全自动磁过滤器

  • SNYQ(U) DN65W-1
  • 珠海市2016年6月信息价
  • 建筑工程
查看价格

全自动磁过滤器

  • SNYQ(U) DN80W-1
  • 珠海市2016年6月信息价
  • 建筑工程
查看价格

全自动磁过滤器

  • SNYQ(U) DN80W-1
  • 珠海市2016年5月信息价
  • 建筑工程
查看价格

全自动磁过滤器

  • SNYQ(U) DN150W-2
  • 珠海市2016年5月信息价
  • 建筑工程
查看价格

VGA转分量信号线

  • TS-9005AV VGA转分量信号线
  • 6.0块
  • 1
  • ITC
  • 不含税费 | 不含运费
  • 2016-03-04
查看价格

底漆

  • 底漆
  • 2205.06kg
  • 3
  • 中档
  • 不含税费 | 不含运费
  • 2019-01-28
查看价格

VGA转分量信号线

  • TS-9005AV VGA转分量信号线,线长50cm
  • 2.0块
  • 1
  • ITC
  • 不含税费 | 不含运费
  • 2016-03-04
查看价格

VGA转分量信号线

  • TS-9005AV VGA转分量信号线,支持VGA、BNC等视频接口
  • 10.0块
  • 1
  • ITC
  • 不含税费 | 不含运费
  • 2016-03-04
查看价格

连通口安装

  • 1.名称:连通口安装2.口径规格:DN503.型号:SP10304.材质:PVC材质
  • 6个
  • 3
  • 主品牌喜活,以下或南山工务局选2家北京恒动、江苏恒泰、浙江金
  • 中档
  • 含税费 | 含运费
  • 2019-04-22
查看价格

强连通分量总结

做一个总结:Kosaraju算法的第二次深搜隐藏了一个拓扑性质,而Tarjan算法和Gabow算法省略了第二次深搜,所以,它们不具有拓扑性质。Tarjan算法用堆栈和标记,Gabow用两个堆栈(其中一个堆栈的实质是代替了Tarjan算法的标记部分)来代替Kosaraju算法的第二次深搜,所以只用一次深搜,效率比Kosaraju算法要高。

查看详情

强连通分量Kosaraju算法思路

这个算法可以说是最容易理解,最通用的算法,其比较关键的部分是同时应用了原图G和反图GT。步骤1:先用对原图G进行深搜形成森林(树),步骤2:然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是EAB存在于反图GT),能遍历到的顶点就是一个强连通分量。余下部分和原来的森林一起组成一个新的森林,继续步骤2直到 没有顶点为止。

改进思路:

当然,基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时,可能深搜到其他树上去,这是不允许的,强连通分量只能存在单棵树中(由开篇第一句话可知)),我们当然不这么做,我们可以巧妙的选择第二深搜选择的树的顺序,使其不可能深搜到其他树上去。想象一下,如果步骤2是从森林里选择树,那么哪个树是不连通(对于GT来说)到其他树上的呢?就是最后遍历出来的树,它的根节点在步骤1的遍历中离开时间最晚,而且可知它也是该树中离开时间最晚的那个节点。这给我们提供了很好的选择,在第一次深搜遍历时,记录时间i离开的顶点j,即numb[i]=j。那么,我们每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于GT来说)就可以了。每次深搜都得到一个强连通分量。

隐藏性质:

分析到这里,我们已经知道怎么求强连通分量了。但是,大家有没有注意到我们在第二次深搜选择树的顺序有一个特点呢?如果在看上述思路的时候,你的脑子在思考,相信你已经知道了!!!它就是:如果我们把求出来的每个强连通分量收缩成一个点,并且用求出每个强连通分量的顺序来标记收缩后的节点,那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。为什么呢?首先,应该明确搜索后的图一定是有向无环图呢?废话,如果还有环,那么环上的顶点对应的所有原来图上的顶点构成一个强连通分量,而不是构成环上那么多点对应的独自的强连通分量了。然后就是为什么是拓扑序列,我们在改进分析的时候,不是先选的树不会连通到其他树上(对于反图GT来说),也就是后选的树没有连通到先选的树,也即先出现的强连通分量收缩的点只能指向后出现的强连通分量收缩的点。那么拓扑序列不是理所当然的吗?这就是Kosaraju算法的一个隐藏性质。

伪代码

Kosaraju_Algorithm:

step1:对原图G进行深度优先遍历,记录每个节点的离开时间。

step2:选择具有最晚离开时间的顶点,对反图GT进行遍历,删除能够遍历到的顶点,这些顶点构成一个强连通分量。

step3:如果还有顶点没有删除,继续step2,否则算法结束。

实现代码

C++

查看详情

强连通分量常见问题

查看详情

强连通分量Gabow算法思路

这个算法其实就是Tarjan算法的变异体,我们观察一下,只是它用第二个堆栈来辅助求出强连通分量的根,而不是Tarjan算法里面的indx[]和mlik[]数组。那么,我们说一下如何使用第二个堆栈来辅助求出强连通分量的根。

我们使用类比方法,在Tarjan算法中,每次mlik[i]的修改都是由于环的出现(不然,mlik[i]的值不可能变小),每次出现环,在这个环里面只剩下一个mlik[i]没有被改变(深度最低的那个),或者全部被改变,因为那个深度最低的节点在另一个环内。那么Gabow算法中的第二堆栈变化就是删除构成环的节点,只剩深度最低的节点,或者全部删除,这个过程是通过出栈来实现,因为深度最低的那个顶点一定比前面的先访问,那么只要出栈一直到栈顶那个顶点的访问时间不大于深度最低的那个顶点。其中每个被弹出的节点属于同一个强连通分量。那有人会问:为什么弹出的都是同一个强连通分量?因为在这个节点访问之前,能够构成强连通分量的那些节点已经被弹出了,这个对Tarjan算法有了解的都应该清楚,那么Tarjan算法中的判断根我们用什么来代替呢?想想,其实就是看看第二个堆栈的顶元素是不是当前顶点就可以了。

现 在,你应该明白其实Tarjan算法和Gabow算法其实是同一个思想的不同实现,但是,Gabow算法更精妙,时间更少(不用频繁更新mlik[])。

伪代码

Gabow_Algorithm:

步骤1:

找一个没有被访问过的节点v,goto step2(v)。否则,算法结束。

步骤2(v):

将v压入堆栈stk1[]和stk2[]

对于v所有的邻接顶点u:

1) 如果没有访问过,则step2(u)

2) 如果访问过,但没有删除,维护stk2[](处理环的过程)

如果stk2[]的顶元素==v,那么输出相应的强连通分量

实现代码

查看详情

强连通分量文献

三通分料阀 三通分料阀

三通分料阀

格式:pdf

大小:2.1MB

页数: 6页

三通分料阀 使 用 说 明 书 永嘉县江北巨锋阀门厂 产品名称; 正三通溜子 三通分料阀、正三通 分料阀 产品型号: Dy/D/Q/S/ FC-I ,FC-II 产品规格: 200*200-900*900 适用介质 :粉料、含尘固体颗粒 适用温度:≤ 350℃ 产品说明: 本阀又名叫正三通分料 阀,是我厂根据固体颗粒和粉状物料 输送的特殊要求而开发的系列产品, 本阀主要由阀体、阀轴、阀板、曲柄 机构、电动推杆 (电液动推杆、气动推 杆或手动机构 )等组成。具有体积小、 重量轻、耐磨性能好、使用寿命长、 阻力小,是利用电动推杆、电液动推 杆、气动推杆驱动,可以快速切换物 料流向。是物料输送系统中控制物料 快速换向的理想设备,广泛应用于建 材、冶金、矿山、轻工、粮食等行业 固体颗粒和粉状物料输送。 型号编 制说明: D—电动推杆 S—手动 Dy —电液动推杆 Q—气动推杆 Fc—分 料阀

暖通分部工程 暖通分部工程

暖通分部工程

格式:pdf

大小:2.1MB

页数: 3页

暖通分部工程 1、工程内容 本工程的通风工程主要包括通风系统、防排烟系统等。 2、施工程序及技术要求 (1)施工主要程序 本工程暖通安装的风管采用镀锌钢板。 ①镀锌钢板风管制作工艺流程: ②镀锌钢板风管安装工序 ③风机安装工艺流程 (2)主要的施工方法和技术要求 ①镀锌钢板风管制作: 镀锌钢板风管一般根据设计图纸,设计变更和现场测量数据在加工厂制作加工,加工厂 设于地下室,剪板机、咬口机、折方机、工作平台等设备成一流水线放置,风管加工好后按 照安装的顺序集中堆放,堆放场地应平稳、干燥、清洁。 镀锌钢板风管与配件的壁厚要求 镀锌钢板风管与配件的壁厚( mm) 风 管 直 径 或 长 边 尺 寸 圆 形 风 管 矩 形 风 管 ≤ 3200.50.5320~4500.60.6450~6300.750.6630~10000.750.751000~12501.01.01320~20001.21 .

连通分量其他信息

有向图的最大强连通子图称为该有向图的强连通分量。

强连通图只有一个强连通分量,即本身,非强连通图有多个强连通分量。

任何连通图的连通分量只有一个,即为其本身。

查看详情

强连通算法

直接根据定义,用双向遍历取交集的方法求强连通分量,时间复杂度为O(N^2+M)。更好的方法是Kosaraju算法或Tarjan算法,两者的时间复杂度都是O(N+M)。本文介绍的是Tarjan算法。

强连通分量

Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

定义DFN(u)为节点u搜索的次序编号(时间戳),Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出,

Low(u)=Min{DFN(u),Low(v),(u,v)为树枝边,u为v的父节点

DFN(v),(u,v)为指向栈中节点的后向边(非横叉边)}

当DFN(u)=Low(u)时,以u为根的搜索子树上所有节点是一个强连通分量。

算法伪代码如下

tarjan(u)

{

DFN[u]=Low[u]=++Index // 设定次序编号和Low初值

Stack.push(u) // 将节点u压入栈中

for each (u, v) in E // 枚举每一条边

if (v is not visted) // 如果节点v未被访问过

tarjan(v) // 继续向下找

Low[u] = min(Low[u], Low[v])

else if (v in S) // 如果节点v还在栈内

Low[u] = min(Low[u], DFN[v])

if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根

repeat

v = S.pop // 将v退栈,为该强连通分量中一个顶点

print v

until (u== v)

}

接下来是对算法流程的演示。

从节点1开始DFS,把遍历到的节点加入栈中。搜索到节点u=6时,DFN[6]=LOW[6],找到了一个强连通分量。退栈到u=v为止,{6}为一个强连通分量。

返回节点5,发现DFN[5]=LOW[5],退栈后{5}为一个强连通分量。

返回节点3,继续搜索到节点4,把4加入堆栈。发现节点4像节点1的后向边,节点1还在栈中,所以LOW[4]=1。节点6已经出栈,不再访问6,返回3,(3,4)为树枝边,所以LOW[3]=LOW[4]=1。

继续回到节点1,最后访问节点2。访问边(2,4),4还在栈中,所以LOW[2]=4。返回1后,发现DFN[1]=LOW[1],把栈中节点全部取出,组成一个连通分量{1,3,4,2}。

至此,算法结束。经过该算法,求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。

可以发现,运行Tarjan算法的过程中,每个顶点都被访问了一次,且只进出了一次堆栈,每条边也只被访问了一次,所以该算法的时间复杂度为O(N+M)。

求有向图的强连通分量还有一个强有力的算法,为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法,其时间复杂度也是 O(N+M)。与Trajan算法相比,Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS,不用建立逆图,更简洁。 在实际的测试中,Tarjan算法的运行效率也比Kosaraju算法高30%左右。此外,该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法,也有助于深入理解求双连通分量的Tarjan算法,两者可以类比、组合理解。

双连通分量

求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法,以及求最近公共祖先的离线Tarjan算法,在此对Tarjan表示崇高的敬意。

void tarjan(int i)

{

int j;

DFN=LOW=++Dindex;

instack=true;

Stap[++Stop]=i;

for (edge *e=V;e;e=e->next)

{

j=e->t;

if (!DFN[j])

{

tarjan(j);

if (LOW[j]<LOW)

LOW=LOW[j];

}

else if (instack[j] && DFN[j]<LOW)

LOW=DFN[j];

}

if (DFN==LOW)

{

Bcnt++;

do

{

j=Stap[Stop--];

instack[j]=false;

Belong[j]=Bcnt;

}

while (j!=i);

}

}

void solve()

{

int i;

Stop=Bcnt=Dindex=0;

memset(DFN,0,sizeof(DFN));

for (i=1;i<=N;i++)

if (!DFN)

tarjan(i);

}

连通分量:无向图 G的一个极大连通子图称为 G的一个连通分量(或连通分支)。连通图只有一个连通分量,即其自身;非连通的无向图有多个连通分量。

强连通图:有向图 G=(V,E) 中,若对于V中任意两个不同的顶点 xy,都存在从xy以及从 yx的路径,则称 G是强连通图。相应地有强连通分量的概念。强连通图只有一个强连通分量,即是其自身;非强连通的有向图有多个强连分量。

单向连通图:设G=<V,E>是有向图,如果u->v意味着图G至多包含一条从u到v的简单路径,则图G为单连通图。

弱连通图:将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。

初级通路:通路中所有的顶点互不相同。初级通路必为简单通路,但反之不真。

相关推荐

  • 相关百科
  • 相关知识
  • 相关专栏
立即注册
免费服务热线: 400-888-9639