强连通分量

✍ dations ◷ 2025-07-11 21:05:40 #强连通分量

强连通分量(英语:Strongly connected component)是图论中的概念。图论中,强连通图指每一个顶点皆可以经由该图上的边抵达其他的每一个点的有向图。意即对于此图上每一个点对(Va,Vb),皆存在路径Va→Vb以及Vb→Va。强连通分量则是指一张有向图G的极大强连通子图G'。如果将每一个强连通分量缩成一个点,则原图G将会变成一张有向无环图。一张图被称为有向无环图当且仅当此图不具有点集合数量大于一的强连通分量,因为有向环即是一个强连通分量,而且任何的强连通分量皆具有至少一个有向环。

Kosaraju算法、Tarjan算法、Gabow算法(英语:Gabow's algorithm)皆为寻找有向图强连通分量的有效算法。但是由于在Tarjan算法和Gabow算法的过程中,只需要进行一次的深度优先搜索,因而相对Kosaraju算法较有效率。

另一类常用的算法 是基于连通性查询的分支算法实现。在串行的情况下算法的复杂度为O( log ),但是却可以达到很好的并行性。Blelloch等人证明了此算法在最坏情况下依然有很高的并行度(算法的span(英语:Analysis of parallel algorithms)仅为 log2 次查询)。

寻找强连通分量的算法,也可以用来解2-SAT(英语:2-satisfiability)(2-satisfiability)问题。Aspvall,Plass & Tarjan (1979)

根据Robbins理论(英语:Robbins' theorem),当一个无向图为双连接图时,也会形成强连通。

相关

  • 斯特林堡奥古斯特·斯特林堡(瑞典语:August Strindberg,1849年1月22日-1912年5月14日)是一位瑞典作家、剧作家和画家,被称为现代戏剧创始人之一。 斯特林堡是一位多产的作家,在其四十余年的
  • 莒国,中国历史上春秋战国时代的一个诸侯国,国君为己姓,源自轩辕黄帝,建国于前1046年,建国君主是兹舆期。公元前431年为楚所灭,但是莒国的全境后来为齐国占领。《汉书·地理志》记
  • 血部血部,为汉字索引中的部首之一,康熙字典214个部首中的第一百四十三个个)。就繁体和简体中文中,血部归于六划部首。血部通常从左、上、下方为部字。且无其他部首可用者将部首归为
  • 约瑟夫·斯发基斯约瑟夫·斯发基斯(英语:Joseph Sifakis,希腊语:Ιωσήφ Σηφάκης,1946年12月26日-)是一名希腊计算机科学家和他也有法国国籍 。2007年,他与爱德蒙·克拉克和艾伦·爱默生一
  • 艾伦·希克斯艾伦·希克斯(英语:Aaron Hicks,1989年10月2日-),美国棒球选手,守备位置为外野手,目前效力美国职棒大联盟的纽约洋基队。2008年被明尼苏达双城队在第一轮第14顺位选入,小联盟时期曾四
  • 赛义德·穆尔塔扎·阿里赛义德·穆尔塔扎·阿里(孟加拉语:সৈয়দ মুর্তাজা আলী,Syed Murtaza Ali;1902年7月1日-1981年8月9日),孟加拉国作家、历史学家。他是赛义德·穆杰塔巴·阿里的哥哥
  • 第87届奥斯卡金像奖最佳动画短片角逐名单←第86届 - 第87届 - 第88届→本条目是第87届奥斯卡金像奖最佳动画短片奖的角逐名单。美国电影艺术与科学学会自1930年设立该奖以来,每年都会邀请各动画制作公司提交他们当年
  • 高尔宣高尔宣(英语:OSN Gao,1997年6月14日-),台湾男歌手、饶舌歌手及词曲作家,创作多以饶舌加上抒情之情歌风格为主,2018年底与娄峻硕SHOU、 ChrisFlow唐仲彣、RĒD°芮德四人组成饶舌团体
  • 远东州远东州是1922年11月15日至1926年1月4日苏联俄罗斯苏维埃社会主义联邦共和国在远东太平洋地区的行政区划。州府在赤塔,1924年迁哈巴罗夫斯克。随着日本干涉军退出俄罗斯远东大
  • 高居翰詹姆斯·卡希尔(英语:James Cahill,1926年8月13日-2014年2月14日),汉名高居翰,美国加利福尼亚州人,美国汉学家。毕业于加州大学伯克利分校东方语言学系本科毕业,1952年和1958年分获密歇根大学安娜堡分校艺术史硕士、博士学位,求学于罗樾,后在瑞典等地工作。之后返回美国,供职于华盛顿弗利尔美术馆、加州大学伯克利分校艺术史教授。2014年2月去世。