精华内容
下载资源
问答
  • Kosaraju

    2019-10-06 14:22:39
    有向图强连通分量算法,包括Kosaraju算法,Tarjin算法,Gabow算法,本文介绍Kosaraju算法。 Kosaraju算法需要对图进行两遍dfs。 step1:对原图G进行深度优先遍历,记录每个节点的离开时间(后序遍历,将点压栈)。 ...

    有向图强连通分量算法,包括Kosaraju算法,Tarjin算法,Gabow算法,本文介绍Kosaraju算法。
    Kosaraju算法需要对图进行两遍dfs。
    step1:对原图G进行深度优先遍历,记录每个节点的离开时间(后序遍历,将点压栈)。
    step2:选择具有最晚离开时间的顶点(出栈),对逆图GT进行遍历,删除能够遍历到的顶点,这些顶点构成一个强连通分量。(如果顶点s和t在G中是互达的,当且仅当s和t在GT中也是互达的。)
    step3:如果还有顶点没有删除,继续step2,否则算法结束。

    void dfs1(int i){
        vis[i]=1;
        for(int j=0;j<G[i].size();j++){
            if(!vis[G[i][j]]){
                dfs1(G[i][j]);
            }
        }
        st[top++]=i;//时间顺序,后序遍历
    }
    void dfs2(int i){
        vis[i]=1;
        kind[i]=k;//k -> 当前联通分量编号
        for(int j=0;j<G_T[i].size();j++){
            if(!vis[G_T[i][j]]){
                dfs2[G_T[i][j]];
            }
        }
    }
    int main(){
        st[n]={0};//stack
        fill(v,v+n+1,0);
        for(int i=1;i<=n;i++){
            if(!vis[i])
                dfs1(i);
        }
        fill(v,v+n+1,0);
        while(--top>=0){
            if(!vis[i]){
                k++;//当前连通分量的编号
                dfs2(st[top]);
            }
        }
    }

    转载于:https://www.cnblogs.com/SilverChen/p/9652249.html

    展开全文
  • kosaraju

    2019-07-16 13:09:00
    void kosaraju(int u){ vis[u]=true; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(!vis[v]){ kosaraju(v); } } f[u].val=++rt; } void rkosaraju(int u){ vis[u]=true; for(int i=...
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    #include<ctime>
    using namespace std;
    const int N=10005;
    int n,m,cnt,rcnt,head[N],rhead[N],t,rt,ans;
    bool vis[N],rvis[N];
    struct Node{
        int u,v,next;
    }edge[N];
    struct rNode{
        int u,v,next;
    }redge[N];
    struct Node1{
        int id,val;
    }f[N];
    bool cmp(Node1 p,Node1 q){
        return p.val>q.val;
    }
    void push(int u,int v){
        ++cnt;
        edge[cnt].u=u;
        edge[cnt].v=v;
        edge[cnt].next=head[u];
        head[u]=cnt;
    }
    void rpush(int u,int v){
        ++rcnt;
        redge[rcnt].u=u;
        redge[rcnt].v=v;
        redge[rcnt].next=rhead[u];
        rhead[u]=rcnt;
    }
    void kosaraju(int u){
        vis[u]=true;
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].v;
            if(!vis[v]){
                kosaraju(v);
            }
        }
        f[u].val=++rt;
    }
    void rkosaraju(int u){
        vis[u]=true;
        for(int i=rhead[u];i!=-1;i=redge[i].next){
            int v=redge[i].v;
            if(!vis[v]){
                rkosaraju(v);
            }
        }
    }
    int main(){
        memset(head,-1,sizeof(head));
        memset(rhead,-1,sizeof(rhead));
        memset(vis,false,sizeof(vis));
        int u,v;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            push(u,v);
            rpush(v,u);
        }
        for(int i=1;i<=n;i++){
            f[i].id=i;
            if(!vis[i]){
                kosaraju(i);
            }
        }
        memset(vis,false,sizeof(vis));
        sort(f+1,f+1+n,cmp);
        for(int i=1;i<=n;i++){
            if(!vis[f[i].id]){
                rkosaraju(f[i].id);
                ++ans;
            }
        }
        printf("%d",ans);
        return 0;
    }

    转载于:https://www.cnblogs.com/ukcxrtjr/p/11194243.html

    展开全文
  • Kosaraju算法详解

    2020-08-29 11:10:00
    主要为大家详细介绍了Kosaraju算法,Kosaraju算法可以计算出一个有向图的强连通分量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • kosaraju算法

    2014-03-26 17:10:09
    kosaraju算法.txt
  • Kosaraju算法

    2019-08-21 11:42:34
    Kosaraju算法 题目 思路:建一个反图,从最后的强连通分量遍历。如果所有点都被访问过了,那么最后一个强连通分量中点的个数就是答案,否则没有。 #include<bits/stdc++.h> using namespace std; #define maxn...

    Kosaraju算法

    题目
    思路:建一个反图,从最后的强连通分量遍历。如果所有点都被访问过了,那么最后一个强连通分量中点的个数就是答案,否则没有。

    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 10010
    int m,n,nl,mmp,sum,cmp[maxn];
    vector<int> g[maxn],rg[maxn],vs;
    bool used[maxn];
    void add(int a,int b){
       g[a].push_back(b); 
       rg[b].push_back(a);//反图
    }
    void dfs(int v) {
       used[v]=1;
       for(int i=0;i<g[v].size();i++){
           if(!used[g[v][i]])
           dfs(g[v][i]);
       }
       vs.push_back(v);
    }//没有访问过就搜索,然后压入vs
    void rdfs(int v,int k){
       used[v]=1;
       cmp[v]=k;
       for(int i=0;i<rg[v].size();i++){
           if(!used[rg[v][i]])
           rdfs(rg[v][i],k);
       }
    }
    int scc(){
       memset(used,0,sizeof(used));
       vs.clear();
       for(int i=1;i<=n;i++)
       	if(!used[i])
       		dfs(i);
       memset(used,0,sizeof(used));
       int k=0;
       for(int i=vs.size()-1;i>=0;i--)
       	if(!used[vs[i]])
       		rdfs(vs[i],k++);
       return k;
    }//k为强连通分量个数
    int main(){
       int u,p;
       cin>>n>>m;
       for(int i=1;i<=m;i++)
       	cin>>u>>p,add(u,p);
       int ans=scc();
       for(int i=1;i<=n;i++)
       	if(cmp[i]==ans-1){
               mmp=i;
               sum++;
           }
       memset(used,0,sizeof(used));
       rdfs(mmp,1);
       for(int i=1;i<=n;i++)
           if(!used[i]){
               cout<<0<<endl;
               return 0;
           }
       cout<<sum<<endl;
       return 0;                                                                                                                                  
    }
    
    展开全文
  • Kosaraju 算法

    2016-09-18 00:18:00
    Kosaraju 算法 一.算法简介 在计算科学中,Kosaraju的算法(又称为–Sharir Kosaraju算法)是一个线性时间(linear time)算法找到的有向图的强连通分量。它利用了一个事实,逆图(与各边方向相同的图形反转, ...

    Kosaraju 算法

    一.算法简介

    在计算科学中,Kosaraju的算法(又称为–Sharir Kosaraju算法)是一个线性时间(linear time)算法找到的有向图强连通分量。它利用了一个事实,逆图(与各边方向相同的图形反转, transpose graph)有相同的强连通分量的原始图。

    有关强连通分量的介绍在之前Tarjan 算法中:Tarjan Algorithm

    逆图(Tranpose Graph ):

    我们对逆图定义如下:

          GT=(V, ET),ET={(u, v):(v, u)∈E}}

    上图是有向图G , 和图G的逆图 G

     摘录维基百科上对Kosaraju Algorithm 的描述:

    (取自https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm)

    • For each vertex u of the graph, mark u as unvisited. Let L be empty.
    • For each vertex u of the graph do Visit(u), where Visit(u) is the recursive subroutine:
      If  u is unvisited then:
      1. Mark u as visited.
      2. For each out-neighbour v of u, do Visit(v).
      3. Prepend u to L.
      Otherwise do nothing.
    • For each element u of L in order, do Assign(u,u) where Assign(u,root) is the recursive subroutine:
      If  u has not been assigned to a component then:
      1. Assign u as belonging to the component whose root is root.
      2. For each in-neighbour v of u, do Assign(v,root).
      Otherwise do nothing.

    通过以上的描述我们发现,Kosaraju 算法就是分别对原图G 和它的逆图 GT 进行两遍DFS,即:

    1).对原图G进行深度优先搜索,找出每个节点的完成时间(时间戳)

    2).选择完成时间较大的节点开始,对逆图GT 搜索,能够到达的点构成一个强连通分量

    3).如果所有节点未被遍历,重复2). ,否则算法结束;

     

    二.算法图示

    上图是对图G,进行一遍DFS的结果,每个节点有两个时间戳,即节点的发现时间u.d完成时间u.f

    我们将完成时间较大的,按大小加入堆栈

    1)每次从栈顶取出元素

    2)检查是否被访问过

    3)若没被访问过,以该点为起点,对逆图进行深度优先遍历

    4)否则返回第一步,直到栈空为止

     

    [ATTENTION] : 对逆图搜索时,从一个节点开始能搜索到的最大区块就是该点所在的强连通分量。

    从节点1出发,能走到  2 ,3,4 , 所以{1 , 2 , 3 , 4 }是一个强连通分量

    从节点5出发,无路可走,所以{ 5 }是一个强连通分量

    从节点6出发,无路可走,所以{ 6 }是一个强连通分量

    自此Kosaraju Algorithm完毕,这个算法只需要两遍DFS即可,是一个比较易懂的求强连通分量的算法。

     

    STRONG-CONNECTED-COMPONENTS ( GRAPH G )
    1 call DFS(G) to compute finishing times u.f for each vertex u
    2 compute GT
    3 call DFS (GT) , but in the main loop of DFS , consider the vertices
             in order of decreasing u.f ( as computed in line 1 )
    4 output the vertices of each tree in the depth-first forest formed in line 3 as a
             separate strongly-connected-componet

     

    三.算法复杂度

    邻接表:O(V+E)

    邻接矩阵:O(V2)

     该算法在实际操作中要比Tarjan算法要慢

    四.算法模板&注释代码

     

     1 #include "cstdio"
     2 #include "iostream"
     3 #include "algorithm"
     4 
     5 using namespace std ;
     6 
     7 const int maxN = 10010 , maxM = 50010;
     8 
     9 struct Kosaraju { int to , next ; } ;
    10 
    11 Kosaraju E[ 2 ][ maxM ] ;
    12 bool vis[ maxN ];
    13 int head[ 2 ][ maxN ] , cnt[ 2 ] , ord[maxN] , size[maxN] ,color[ maxN ];
    14 
    15 int tot , dfs_num  , col_num , N , M  ;
    16 
    17 void Add_Edge( int x , int y , int _ ){//建图 
    18          E[ _ ][ ++cnt[ _ ] ].to = y ;
    19          E[ _ ][ cnt[ _ ] ].next = head[ _ ][ x ] ;
    20          head[ _ ][ x ] = cnt[ _ ] ;
    21 }
    22 
    23 void DFS_1 ( int x , int _ ){
    24          dfs_num ++ ;//发现时间 
    25          vis[ x ] = true ;
    26          for ( int i = head[ _ ][ x ] ; i ; i = E[ _ ][ i ].next ) {
    27                  int temp = E[ _ ][ i ].to;
    28                  if(vis[ temp ] == false) DFS_1 ( temp , _ ) ;
    29          }
    30          ord[(N<<1) + 1 - (++dfs_num) ] = x ;//完成时间加入栈 
    31 }
    32 
    33 void DFS_2 ( int x , int _ ){
    34          size[ tot ]++ ;// 强连通分量的大小 
    35          vis[ x ] = false ;
    36          color[ x ] = col_num ;//染色 
    37          for ( int i=head[ _ ][ x ] ; i ; i = E[ _ ][ i ].next ) {
    38                  int temp = E[ _ ][ i ].to;
    39                  if(vis[temp] == true) DFS_2(temp , _);
    40          } 
    41 }
    42 
    43 int main ( ){
    44          scanf("%d %d" , &N , &M );
    45          for ( int i=1 ; i<=M ; ++i ){
    46                  int _x , _y ;
    47                  scanf("%d %d" , &_x , &_y ) ;
    48                  Add_Edge( _x , _y , 0 ) ;//原图的邻接表 
    49                  Add_Edge( _y , _x , 1 ) ;//逆图的邻接表 
    50          }
    51          for ( int i=1 ; i<=N ; ++i ) 
    52                  if ( vis[ i ]==false ) 
    53                           DFS_1 ( i , 0 ) ;//原图的DFS 
    54 
    55          for ( int i = 1 ; i<=( N << 1) ; ++i ) {
    56                  if( ord[ i ]!=0 && vis[ ord[ i ] ] ){
    57                           tot ++ ; //强连通分量的个数 
    58                           col_num ++ ;//染色的颜色 
    59                           DFS_2 ( ord[ i ] , 1 ) ;
    60                  }
    61          }
    62          
    63          for ( int i=1 ; i<=tot ; ++i )
    64                  printf ("%d ",size[ i ]);
    65          putchar ('\n');
    66          for ( int i=1 ; i<=N ; ++i )
    67                  printf ("%d ",color[ i ]);
    68          return 0;
    69 }

     

    2016-09-18 00:16:19

    (完)

    转载于:https://www.cnblogs.com/shadowland/p/5876307.html

    展开全文
  • Kosaraju算法学习

    2019-01-01 16:31:00
    Kosaraju 算法学习 序 这星期捣鼓了一个新的算法——Kosaraju算法 今天分享给大家 简介 Kosaraju算法,其实与tarjan算法差不多。但是码量较小,容易记忆。其时间复杂度与tarjan算法一样,为O(n+m),所以,某种程度上...
  • kosaraju 算法 Kosaraju 算法是一种线性时间算法,用于查找有向图的强连通分量 算法 Kosaraju 算法的工作原理如下: 设 G 为有向图,S 为空栈。 虽然 S 不包含所有顶点: 选择不在 S 中的任意顶点 ''v''。从 ''v''...
  • kosaraju_sat2_solver-源码

    2021-05-15 14:24:12
    kosaraju_sat2_solver
  • kosaraju算法 上次我给出数学推理来证明Dijkstra的算法。 这次,我为Kosaraju算法提供了一种可能的实现方式,该算法可在有向图中找到强连接的组件。 “牢固连接的组件”的简称是SCC 程序的目的 。 ===============...
  • 文章目录前言正题一些必要概念Kosaraju如和实现Why?如何理解问题 前言 今天想起来Kosaraju,网上关于这个算法的介绍比较少。(毕竟Tarjan太强了)。但是Tarjan和Kosaraju的复杂度都是O(n)O(n)O(n)的,Kosaraju的...
  • 图论 —— 图的连通性 —— Kosaraju 算法.pdf
  • Kosaraju算法用来解决有向图的连通性问题,算法的基本步骤: 1.对一幅有向图G,计算它的反向图GR的逆后序排列(一次dfs)。 2.按由1计算得到的顺序对G进行dfs操作,来访问所有未被标记的顶点。 3.在构造函数中,...
  • kosaraju算法
  • Kosaraju's algorithm

    2019-09-28 02:38:16
    推荐到我的这篇博客中看完整版的。... 算法实现摘自Kosaraju's algorithm - 百度百科: #include <iostream> #include <stack> using namespace std; int map[511][511]; int nma...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,130
精华内容 852
关键字:

kosaraju