Kosaraju算法

✍ dations ◷ 2025-05-23 03:25:08 #图算法

Kosaraju算法(也被称为Kosaraju–Sharir算法)是一个在线性时间内寻找一个有向图中的强连通分量的算法。阿尔佛雷德·艾侯,约翰·霍普克洛夫特和杰弗里·乌尔曼(英语:Jeffrey D. Ullman)相信该算法来自S. Rao Kosaraju(英语:S. Rao Kosaraju)于1978年撰写的一篇未发表论文之中。米卡·夏尔(英语:Micha Sharir)也独立发现了该算法并于1981年将其发表。该算法巧妙地利用了一个定理:“一个图的反向图和原图具有一样的强连通分量”。

该算法主要用于枚举图中每一个强连通分量内的所有顶点。该算法可由以下四部分组成:

public class KosarajuAlgorithm {    private boolean marked;    private int id;    private int count=-1;    private Stack<Integer> reversePostOrder;    public KosarajuAlgorithm(Digraph G){        //G.V()返回有向图G的边数        marked=new boolean;        id=new int;        //G.reverse()返回的为G的反向图        Digraph G_reverse=G.reverse();        //本遍循环是将G的反向图的逆后序排列存储在reversePostOrder中        for(int i=0;i<G_reverse.V();i++){            if(!marked){                dfs(G_reverse,i);            }        }        count=0;        //按照G的反向图的逆后排序进行深度优先搜索        for(int i:reversePostOrder){            if(!marked){                dfs(G,i);                count++;            }        }    }    //深度优先搜索    public void dfs(Digraph G,int v){        marked=true;        id=count;        for(int i:G.adj(v)){            if(!marked){                dfs(G,i);            }        }        reversePostOrder.push(v);    }}

复杂度

当图是使用邻接表形式组建的,Kosaraju算法需要对整张图进行了两次的完整的访问,每次访问与顶点数 V {\displaystyle V} 和边数 E {\displaystyle E} 之和 V + E {\displaystyle V+E} 成正比,所以可以在线性时间 O ( V + E ) {\displaystyle O(V+E)} 内访问完成。该算法在实际操作中要比Tarjan算法和基于路径的强连通分量算法(英语:Path-based strong component algorithm)要慢,这两种算法都只需要对图进行一次完整的访问。

当图是使用邻接矩阵形式组建的,算法的时间复杂度为 O ( V 2 ) {\displaystyle O(V^{2})}

相关

  • 太瑞县太瑞县(越南语:Huyện Thái Thụy/.mw-parser-output .han-nom{font-family:"Nom Na Tong","Han-Nom Gothic","Han-Nom Ming","HAN NOM A","HAN NOM B","Ming-Lt-HKSCS-UNI-H"
  • 液化氦液氦(英语:Liquid helium)是指在极低温的摄氏温标-269 °C(约等于热力学温标4 K或者是华氏温标-452.2 °F)时成为液体的氦,该化学元素的沸点与临界点取自于氦的同位素:较为常见的氦
  • 阿里郎阿里郎节是朝鲜官方举办的大型团体操表演活动。通常不定期地在首都平壤的五一体育场举行。阿里郎节以大型团体操的形式展现朝鲜的历史,约有六到十万人参加演出。它通过场面宏
  • 伊利诺伊大学芝加哥分校伊利诺伊大学芝加哥分校(University of Illinois at Chicago,简称UIC),位于美国伊利诺伊州芝加哥,是国家资助的公立研究型大学。它是伊利诺伊大学的第二个成员,是在芝加哥地区最大
  • .cy.cy为塞浦路斯国家及地区顶级域(ccTLD)的域名。该国目前正在申请希腊语顶级域名.κπ。A .ac .ad .ae .af .ag .ai .al .am .ao .aq .ar .as .at .au .aw .ax .az  B .ba
  • 丰花草属丰花草属(学名:)是茜草科下的一个属,为草本或矮小亚灌木植物。该属共有约150种,分布于热带或亚热带地区。
  • 普拉塔加尔县普拉塔加尔县是印度的一个县,位于该国北部,由北方邦负责管辖,面积3,717平方公里,识字率为73.1%,2011年人口3,173,752,人口密度每平方公里854人。
  • 报知新闻社报知新闻社股份有限公司(日语:株式会社報知新聞社)是一家总部设于东京都港区的日本报社,是读卖新闻集团下属的报社之一(但只是由读卖新闻集团本社持股,却不属于本社直属子公司)。报
  • 御裳川公园坐标:33°57′56.9″N 130°57′25.4″E / 33.965806°N 130.957056°E / 33.965806; 130.957056 (御裳川公园)御裳川公园(日文:みもすそ川公園)是位于日本山口县下关市御裳川町
  • 渡边利雄渡边利雄(日语:渡辺 利雄/わたなべ としお  */?,1935年10月1日-2020年1月10日),日本美国文学研究家,英语教育家。东京大学名誉教授。1935年生于日治台湾新竹市。1954年毕业于新潟