青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

O(1) 的小樂

Job Hunting

公告

記錄我的生活和工作。。。
<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

統(tǒng)計(jì)

  • 隨筆 - 182
  • 文章 - 1
  • 評論 - 41
  • 引用 - 0

留言簿(10)

隨筆分類(70)

隨筆檔案(182)

文章檔案(1)

如影隨形

搜索

  •  

最新隨筆

最新評論

閱讀排行榜

評論排行榜

有向圖強(qiáng)連通分量 Kosaraju算法

   It makes use of the fact that the transpose graph (the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.

   它利用了有向圖的這樣一個性質(zhì),一個圖和他的transpose graph(邊全部反向)具有相同的強(qiáng)連通分量!

算法偽代碼

Kosaraju's algorithm is simple and works as follows:

  • Let G be a directed graph and S be an empty stack.
  • While S does not contain all vertices:
    • Choose an arbitrary vertex v not in S. Perform a depth-first search starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.
  • Reverse the directions of all arcs to obtain the transpose graph.
  • While S is nonempty:
    • Pop the top vertex v from S. Perform a depth-first search starting at v. The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently,breadth-first search (BFS) can be used instead of depth-first search.

 

 

需要注意的是這里的第一遍BFS搜索的時(shí)候的入隊(duì)序列,Each time that depth-first search finishes expanding a vertex u, push u onto S.只有當(dāng)擴(kuò)展結(jié)束了此節(jié)點(diǎn)之后,此節(jié)點(diǎn)才會被push onto S.

算法思路:

1, 后序遍歷原圖,對每個訪問到的節(jié)點(diǎn)標(biāo)記時(shí)間戳。

2, 按照時(shí)間戳的降序遍歷反向圖,得到的每個連通塊就是一個強(qiáng)連通分量。

證明是很簡單的:

假設(shè)以上算法從u訪問到了v,那么說明反向圖有一條從u到v的邊,也就說明了原圖中有一條從v到u的邊,又因?yàn)閡的標(biāo)號是大于v的,那么,u一定在v之前訪問到(否則v的標(biāo)號將大于u),并且是從u訪問到v了的(v到u也有一條路徑,否則就會從v訪問到u)。

 

QQ截圖未命名

如果應(yīng)用我們第一個Tarjan算法的例子的話,第一遍DFS 得到的次序是 6 4 2 5 3 1

 

代碼

#include "cstdlib"
#include "cctype"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "vector"
#include "string"
#include "iostream"
#include "sstream"
#include "set"
#include "queue"
#include "stack"
#include "fstream"
#include "strstream"
using namespace std;
#define M 2000
bool vis[M];                 //遍歷數(shù)組
int post[M];                 //時(shí)間戳對應(yīng)的點(diǎn)
int timestamp;               //時(shí)間戳
int ComponetNumber=0;        //有向圖強(qiáng)連通分量個數(shù)
vector <int> Edge[M];        //鄰接表表示
vector <int> Opp[M];         //原圖的反圖
vector <int> Component[M];   //獲得強(qiáng)連通分量結(jié)果

void dfs(int u) {             //第一個dfs確定時(shí)間戳
    vis[u] = true;
    for(int i=0;i<Edge[u].size();i++) {
        if(vis[ Edge[u][i]])    continue;
        //cout<<Edge[u][i]<<endl;
        dfs(Edge[u][i]);
    }
    //cout<<"timestamp    "<<timestamp<<"       "<<u<<endl;   
    post[timestamp++] = u;
}

void dfs2(int u) {      //第二個反邊dfs確定連通塊
    vis[u] = true;
    Component[ComponetNumber].push_back(u);
    for(int i=0;i<Opp[u].size();i++)
    {
        int v = Opp[u][i];
        if(vis[v])  continue;
        dfs2(v);
    }
}

void Kosaraju(int n) {
    memset(vis,0,sizeof(vis));
    timestamp = 0;
    for(int i=0;i<n;i++) {
        if(vis[i])    continue;
        dfs(i);
    }
    memset(vis,0,sizeof(vis));
    ComponetNumber++;
    for(int i=n-1;i>=0;i--) {//按時(shí)間戳從大到小搜
        if(vis[post[i]])    continue;
        Component[ComponetNumber].clear();
        dfs2(post[i]);
        ComponetNumber++;
    }
    ComponetNumber--;      //最后我們把塊加了1。。所以要減掉
}
int main()
{
    Edge[0].push_back(1);Edge[0].push_back(2);
    Edge[1].push_back(3);
    Edge[2].push_back(3);Edge[2].push_back(4);
    Edge[3].push_back(0);Edge[3].push_back(5);
    Edge[4].push_back(5);

    Opp[0].push_back(3);
    Opp[1].push_back(0);
    Opp[2].push_back(0);
    Opp[3].push_back(1);Opp[3].push_back(2);
    Opp[4].push_back(2);
    Opp[5].push_back(3);Opp[6].push_back(4);
    int  N=6;
    Kosaraju(N);
    cout<<"ComponetNumber is "<<ComponetNumber<<endl;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<Component[i].size();j++)
            cout<<Component[i][j];
        cout<<endl;
    }
    return 0;
}

 

 

    此算法的時(shí)間復(fù)雜度當(dāng)然也是 O(M+N)(M條邊,N個點(diǎn))與Tarjan算法相似。。但是在系數(shù)上不如Tarjan算法!在實(shí)際的測試中,Tarjan算法的運(yùn)行效率也比Kosaraju算法高30%左右。 

    當(dāng)然Kosaraju算法額外花費(fèi)的時(shí)間,也不是白費(fèi)的,它獲得了圖的一個拓?fù)湫再|(zhì)哦!!

    如果我們把求出來的每個強(qiáng)連通分量收縮成一個點(diǎn),并且用求出每個強(qiáng)連通分量的順序來標(biāo)記收縮后的節(jié)點(diǎn),那么這個順序其 實(shí)就是強(qiáng)連通分量收縮成點(diǎn)后形成的有向無環(huán)圖的拓?fù)湫蛄?/strong>。為什么呢?首先,應(yīng)該明確搜索后的圖一定是有向無環(huán)圖呢?廢話,如果還有環(huán),那么環(huán)上的頂點(diǎn)對應(yīng) 的所有原來圖上的頂點(diǎn)構(gòu)成一個強(qiáng)連通分量,而不是構(gòu)成環(huán)上那么多點(diǎn)對應(yīng)的獨(dú)自的強(qiáng)連通分量了。然后就是為什么是拓?fù)湫蛄校覀冊诟倪M(jìn)分析的時(shí)候,不是先選 的樹不會連通到其他樹上(對于反圖GT來說),也就是后選的樹沒有連通到先選的樹,也即先出現(xiàn)的強(qiáng)連通分量收縮的點(diǎn)只能指向后出現(xiàn)的強(qiáng)連通分量收縮的點(diǎn)。那么拓?fù)湫蛄胁皇抢硭?dāng)然的嗎?這就是Kosaraju算法的一個隱藏性質(zhì)。

 

Reference :

http://www.notonlysuccess.com/?p=181

推薦一下啊!終于算是搞的差不多了。。下面就是做一些練習(xí),然后鞏固提高一下!接下來剩下的最后一個算法了:Gabow 算法

posted on 2010-09-26 22:49 Sosi 閱讀(1863) 評論(1)  編輯 收藏 引用

評論

# re: 有向圖強(qiáng)連通分量 Kosaraju算法 2013-04-29 19:13 ygqwan

樓主的第一次post數(shù)組是不是存錯了呢
  回復(fù)  更多評論    

只有注冊用戶登錄后才能發(fā)表評論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
      <noscript id="pjuwb"></noscript>
            <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
              <dd id="pjuwb"></dd>
              <abbr id="pjuwb"></abbr>
              亚洲一区999| 欧美一级久久| 久久久午夜电影| 有坂深雪在线一区| 欧美电影电视剧在线观看| 久久久亚洲精品一区二区三区| 黄色精品在线看| 欧美激情免费观看| 性8sex亚洲区入口| 亚洲一区图片| 在线免费观看欧美| 日韩午夜电影| 国产在线国偷精品产拍免费yy| 蜜臀av性久久久久蜜臀aⅴ| 欧美a级片网| 亚洲在线视频免费观看| 久久福利毛片| 亚洲久久一区| 亚洲欧美中日韩| 久久精品国产v日韩v亚洲| 亚洲另类自拍| 国产日韩欧美另类| 亚洲国产欧美久久| 欧美日韩精品二区| 久久亚洲精品一区二区| 欧美精品偷拍| 久久先锋资源| 国产精品日韩欧美一区| 欧美xx视频| 国产欧美精品一区二区三区介绍| 欧美成人中文字幕| 国产农村妇女毛片精品久久麻豆| 欧美成人情趣视频| 国产亚洲女人久久久久毛片| 91久久久亚洲精品| 国内成人在线| 亚洲视频在线免费观看| 亚洲精品国产拍免费91在线| 欧美主播一区二区三区美女 久久精品人| 91久久精品国产91久久性色tv| 亚洲免费在线观看| 亚洲一区二区在线看| 欧美电影免费网站| 美女图片一区二区| 国产日韩亚洲| 亚洲网友自拍| 亚洲一区二区在线看| 欧美区亚洲区| 亚洲人精品午夜| 亚洲精品欧美日韩专区| 久久最新视频| 欧美成人精品高清在线播放| 国外成人在线| 欧美一区二区三区在线播放| 性欧美videos另类喷潮| 国产精品久久久免费| 日韩一区二区免费看| 在线一区欧美| 欧美偷拍另类| 亚洲视频图片小说| 午夜精品久久久久久99热| 国产精品极品美女粉嫩高清在线 | 韩日精品视频| 欧美一区二区在线看| 久久蜜桃精品| 精品成人乱色一区二区| 久久精品一区二区三区中文字幕 | 亚洲免费视频观看| 国产精品久久久久久久久久久久| 夜夜嗨一区二区三区| 亚洲一区制服诱惑| 国产精品亚洲人在线观看| 亚洲男人天堂2024| 久久手机免费观看| 亚洲国产毛片完整版| 欧美精品电影在线| 亚洲色图在线视频| 久久激情视频免费观看| 国内外成人在线| 免费亚洲网站| 亚洲精品日韩久久| 性欧美videos另类喷潮| 狠狠色综合色区| 欧美激情综合色| 亚洲午夜精品久久久久久app| 久久精品99| 亚洲国产成人精品女人久久久| 欧美国产视频日韩| 亚洲欧美精品在线观看| 狂野欧美一区| 亚洲午夜国产一区99re久久| 国产精品色一区二区三区| 久久久久久久久久久久久女国产乱| 欧美成人午夜剧场免费观看| 一本色道久久综合| 国产美女精品一区二区三区| 蜜臀va亚洲va欧美va天堂 | 美女亚洲精品| 亚洲一区二区少妇| 一区二区三区在线视频免费观看 | 久久久久国产精品一区三寸| 亚洲欧洲在线视频| 久久精品99国产精品日本| 亚洲精品在线视频观看| 国产欧美精品日韩精品| 欧美激情影音先锋| 欧美综合二区| 亚洲桃色在线一区| 欧美国产亚洲另类动漫| 久久疯狂做爰流白浆xx| 一本大道久久a久久精二百| 国产主播一区二区| 国产精品高潮呻吟久久| 欧美成人激情视频免费观看| 午夜欧美大尺度福利影院在线看| 91久久精品国产91久久性色| 久久婷婷国产综合尤物精品| 亚洲一区二区在线看| 亚洲狼人综合| 亚洲国产精品电影| 韩国一区二区在线观看| 欧美激情一区三区| 久久精品国产成人| 欧美一级久久久久久久大片| 一区二区三区www| 亚洲国产精品t66y| 伊人久久大香线| 国产综合视频| 国产亚洲激情在线| 国产精品综合不卡av| 欧美视频一二三区| 欧美视频手机在线| 欧美视频在线观看 亚洲欧| 欧美h视频在线| 老司机67194精品线观看| 久久av资源网站| 欧美一区二区三区四区高清| 午夜精品理论片| 午夜伦理片一区| 欧美一级视频一区二区| 欧美亚洲日本网站| 先锋影音国产一区| 欧美中文字幕不卡| 欧美一级免费视频| 久久久99精品免费观看不卡| 欧美专区亚洲专区| 久久久久久午夜| 欧美不卡在线| 欧美日韩国产在线播放网站| 欧美欧美天天天天操| 欧美三区美女| 国产网站欧美日韩免费精品在线观看| 国产精品国产一区二区| 国产精品久久久一本精品| 国产欧美一区二区色老头| 国产日韩专区| 亚洲高清一二三区| 在线视频一区观看| 亚洲欧洲av一区二区三区久久| 欧美一区二区视频在线观看| 久久精品女人| 亚洲国产精品第一区二区三区| 亚洲伦理在线观看| 亚洲在线视频| 久久亚洲精品欧美| 欧美日韩一区在线| 国产综合精品| 最近中文字幕mv在线一区二区三区四区 | 欧美激情精品久久久六区热门| 亚洲清纯自拍| 亚洲一区二区三区精品在线| 久久精品欧美日韩精品| 欧美日韩91| 黄色在线成人| 亚洲天堂成人在线观看| 久久精品国产亚洲a| 亚洲激情自拍| 欧美在线二区| 欧美日韩精品一本二本三本| 国产亚洲a∨片在线观看| 91久久综合| 久久婷婷国产麻豆91天堂| 亚洲裸体视频| 久久九九精品| 国产精品每日更新在线播放网址| 在线欧美日韩精品| 亚洲字幕在线观看| 亚洲二区在线| 欧美一区二区三区四区在线观看| 欧美精品在线一区| 精品成人国产在线观看男人呻吟| 亚洲一区二区伦理| 亚洲国产精品高清久久久| 欧美亚洲在线视频| 国产精品vvv| 日韩亚洲精品电影| 欧美激情影音先锋| 久久国产精品黑丝| 国产精品亚洲综合久久| 夜夜嗨av一区二区三区四区|