选择特殊符号

选择搜索类型

热门搜索

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

强连通

强连通在计算机图论中,图G中任意两点都都存在着点V到点V的路径(路径,若途径W中的点和边都不重复,则称为路径) 当然,这是对有向图而言的,无图称为连通.对任意两个顶点 x 和 y ,都存在一条有向路从 x 到 y ,也存在一条有向路从 y 到 x。

强连通基本信息

强连通算法

直接根据定义,用双向遍历取交集的方法求强连通分量,时间复杂度为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);

}

强连通造价信息

  • 市场价
  • 信息价
  • 询价

连通

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

连通口封堵

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

连通

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

粘宝

  • 渗透型(防水胶水);因东北、新疆等地昼夜温差较大的因素,针对东北.新疆等地生产的CGP粘系列产品单价在本站发布的单价基础上增加5元/㎡.
  • kg
  • 桂湖防水
  • 13%
  • 四川鑫桂湖防水保温节能科技有限公司
  • 2022-12-06
查看价格

粘宝

  • 通用型(防水胶水);因东北、新疆等地昼夜温差较大的因素,针对东北.新疆等地生产的CGP粘系列产品单价在本站发布的单价基础上增加5元/㎡.
  • kg
  • 桂湖防水
  • 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月信息价
  • 建筑工程
查看价格

底漆

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

连通口安装

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

声驱离器

  • 声驱离器
  • 9个
  • 1
  • 中档
  • 含税费 | 含运费
  • 2022-09-27
查看价格

启双切开关250V10A(带消防启触点)

  • 启双切开关250V 10A(带消防启触点)
  • 31.62个
  • 2
  • 德力西、西蒙
  • 中档
  • 不含税费 | 含运费
  • 2020-11-17
查看价格

声警号

  • 1.名称:声警号2.其他:详见招标文件及图纸等其他有关文件
  • 27台
  • 1
  • 豪恩
  • 中档
  • 含税费 | 不含运费
  • 2022-03-31
查看价格

强连通图:在有向图中, 若对于每一对顶点v1和v2, 都存在一条从v1到v2和从v2到v1的路径,则称此图是强连通图。

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

强连通简介

在计算机图论中,强连通(Strongly Connected)是指有向图G(Directed Graph)中任意两点v1、v2之间都存在着v1到v2的路径(path,若途径的点和边都不重复,则称为路径)及v2到v1的路径。

定理:

一个有向图是强连通的,当且仅当G中有一个回路,它至少包含每个节点一次。

证明:

充分性

如果G中有一个回路,它至少包含每个节点一次,则G中任两个节点都是互相可达的,故G是强连通图。

必要性

如果有向图是强连通的,则任两个节点都是相互可达。故必可做一回路经过图中所有各点。若不然则必有一回路不包含某一结点v,并且v与回路上的个节点就不是相互可达,与强连通条件矛盾。

有向图

在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。

强连通常见问题

  • 连通管

    必须的,这是恒温三通阀,而且价格不低呢,且三通管也得计算。

  • 板负筋连通布置

    定义温度钢筋,点画。

  • 钢筋的连通

    如果不是同一道梁,一般原则上是不能拉通的,要分别施工

在图论中,连通图基于连通的概念。在一个无向图 G 中,若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径),则称vi和vj是连通的。如果 G 是有向图,那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。如果此图是有向图,则称为强连通图(注意:需要双向都有路径)。图的连通性是图的基本性质。

强连通文献

中低压连通管原理 中低压连通管原理

中低压连通管原理

格式:pdf

大小:192KB

页数: 4页

低压导汽管 中压缸中部引出的蒸汽由两根 Φ900的低压导汽管接到低压缸中部,低压导汽管的结构如图 2—18所示。它是 用钢板卷曲后焊成的薄壁导管,与中压缸和低压缸是直接用法兰刚性连接的。两连接口的中心距为 7895 毫米。在 汽轮机运行时,低压导汽管与汽缸之间商热膨胀色最大工况时约为 16 毫米。为了吸收此膨胀差,在低压导汽管低 压缸处的直管段上设有三节波纹管。 最大工况时低压导汽管内的蒸汽压力为 2.62绝对大气 6,约有 11吨的蒸汽力 作用在波纹管上, 从而增加了管壁中的应力。 因此在低压导汽管的一端设置一个平衡鼓 4。两根 Φ73x 4的蒸汽连管 5使平衡鼓内与低压导汽管内的蒸汽压力相同。 平衡鼓与低压导汽管用三根 Φ45的拉杆 6和一个连接圆筒 7连接起 来,内部蒸汽压力就出这些拉杆和圆筒来承担,不作用在波纹管上 (俗称补偿节 ),见图 2—19 平衡原理示意图。为 了不妨碍在导

城市水系连通与景观设计初探——以黄冈水系连通工程为例 城市水系连通与景观设计初探——以黄冈水系连通工程为例

城市水系连通与景观设计初探——以黄冈水系连通工程为例

格式:pdf

大小:192KB

页数: 5页

在城市水系规划中将景观和城市水利工程融合,是提升城市生态环境的关键。本文以湖北省黄冈市水系连通工程(长河—遗爱湖引水渠)景观设计为例,针对原水系连通工程中景观存在的不足,通过模糊城市蓝线、绿线,让景观与水利相互交融,从碧水相映、文业砚田、幽远溪岸空间对城市水系连通与景观设计融合进行了探索,为城市水系连通工程设计提供新的思路和方法,对于实现水利工作思路从单纯工程建设向人与自然和谐相处转变具有重要参考价值和借鉴意义。

强连通关系(strong connected relation)一种特殊的关系.指任意两个事物之间与其反关系总有一个成立的那种关系.简称六度空间理论,集合A上的二元关系R,对任何a,bEA,有aRb或bRa.用符号表示:R是A上的强连通关系C}(b aEA)(b bEA)(aRbV bRa).当A上关系R是强连通关系时,称R在A上强连通,或称A上关系R有强连通性.例如实数集上关系"镇"是强连通的,而"<"不是强连通的.A上的强连通关系一定是连通关系;若R强连通,则R-'也强连通,且R日R一土=AXA.

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

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

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

一个拓扑空间被认为是局部连通的,如果空间中的每一点的任何一个邻域都包含这个点的一个连通邻域。这里所说的连通邻域,就是指这个邻域所诱导的子拓扑空间按照上面的定义是一个连通空间。 也可以从拓扑基的角度定义局部连通空间:局部连通空间的拓扑基完全是由连通的集合组成的。

相关推荐

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