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

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>
              一区二区日韩精品| 欧美福利电影网| 日韩视频专区| 国产精品久久久久久亚洲毛片| 一本不卡影院| 亚洲欧美国产视频| 国产一区二区高清视频| 欧美成人精品1314www| 欧美成人一区二区在线 | 亚洲欧美另类国产| 国产亚洲综合精品| 欧美v亚洲v综合ⅴ国产v| 美日韩在线观看| 亚洲一本视频| 久久国产加勒比精品无码| 亚洲成人在线| 国产精品99久久久久久www| 国产乱码精品1区2区3区| 免费久久精品视频| 欧美日韩精品在线视频| 欧美在线播放高清精品| 欧美成人午夜剧场免费观看| 亚洲综合第一页| 老司机凹凸av亚洲导航| 亚洲欧美日产图| 美女黄色成人网| 欧美一级欧美一级在线播放| 另类专区欧美制服同性| 亚洲欧美日韩国产综合| 嫩草伊人久久精品少妇av杨幂| 亚洲综合国产精品| 蜜臀91精品一区二区三区| 先锋资源久久| 欧美精品网站| 免费欧美日韩国产三级电影| 国产精品毛片高清在线完整版| 欧美成人免费视频| 国产麻豆一精品一av一免费| 91久久线看在观草草青青| 国产精品日韩专区| 日韩午夜中文字幕| 亚洲第一毛片| 欧美主播一区二区三区| 亚洲综合精品自拍| 欧美日韩成人在线| 亚洲第一久久影院| 在线观看亚洲一区| 欧美在线观看网站| 欧美亚洲综合在线| 欧美四级在线| 亚洲精品美女| 亚洲久久一区| 欧美成年人视频| 欧美成人精品一区| 在线成人黄色| 久久久久国产免费免费| 久久精品亚洲一区二区| 国产精品视频不卡| 亚洲欧美中文日韩v在线观看| 一本久久a久久免费精品不卡| 久久综合给合| 欧美黑人多人双交| 亚洲欧洲在线免费| 免费亚洲电影| 亚洲激情在线视频| 艳女tv在线观看国产一区| 欧美成人免费全部| 最新精品在线| 一区二区三区高清| 欧美性开放视频| 亚洲视频axxx| 久久福利影视| 黄色综合网站| 欧美88av| 日韩网站在线观看| 午夜精品剧场| 国产日韩欧美亚洲| 久久久91精品| 亚洲福利视频二区| 一区二区久久久久| 国产精品一区二区在线观看不卡 | 久久最新视频| 亚洲激情网站免费观看| 欧美精品在线一区二区三区| 亚洲最新色图| 久久久精彩视频| 亚洲国产精品久久久久秋霞不卡| 欧美国产在线视频| 亚洲在线不卡| 欧美xxxx在线观看| 一区二区欧美在线观看| 国产亚洲欧美日韩美女| 男人的天堂亚洲| 一区二区三区高清不卡| 久久综合狠狠综合久久激情| 亚洲精品美女91| 国产精品中文字幕欧美| 久久综合久久综合这里只有精品| 亚洲日本电影| 久久精品在线视频| 亚洲精品中文字幕在线观看| 国产精品一区二区三区四区| 免费在线欧美黄色| 亚洲欧美中文在线视频| 亚洲欧洲日韩女同| 久久久久久久综合日本| 99精品免费视频| 今天的高清视频免费播放成人 | 国产一区二区精品久久| 欧美日韩国产欧| 欧美在线视频免费| 亚洲三级色网| 久久综合久久美利坚合众国| 亚洲永久免费观看| 亚洲人在线视频| 韩国美女久久| 国产精品美女主播在线观看纯欲| 每日更新成人在线视频| 久久成人精品视频| 亚洲一区二区三区在线播放| 亚洲人妖在线| 欧美激情亚洲另类| 久久久中精品2020中文| 午夜精品亚洲| 一区二区三区久久网| 91久久夜色精品国产网站| 韩日精品视频一区| 国产日韩欧美综合| 国产精品一区2区| 国产精品久久久久久av下载红粉| 欧美a级片网| 久久综合一区二区| 久久欧美中文字幕| 久久久精品tv| 久久精品国产久精国产思思| 亚洲欧美视频| 先锋影音网一区二区| 亚洲香蕉网站| 亚洲影院色无极综合| 中国成人黄色视屏| 亚洲视频视频在线| 亚洲性视频h| 亚洲欧美日韩国产精品| 亚洲欧美成人一区二区三区| 亚洲午夜一区二区| 亚洲欧美另类久久久精品2019| 亚洲男人天堂2024| 午夜久久电影网| 久久狠狠一本精品综合网| 久久国产精品久久精品国产| 久久久久国产精品一区二区| 久久午夜电影| 欧美激情一区二区三区四区| 欧美精品黄色| 国产精品久久久久久av福利软件| 国产精品人人做人人爽人人添| 国产精品视频在线观看| 国产亚洲欧洲997久久综合| 韩国v欧美v日本v亚洲v| 亚洲日本精品国产第一区| 日韩视频在线你懂得| 亚洲欧美日韩爽爽影院| 久久久一二三| 亚洲黄页一区| 亚洲欧美精品在线观看| 久久精品免费观看| 欧美精品一卡二卡| 国产美女精品视频| 亚洲国产精品成人综合| 亚洲图片你懂的| 久久久蜜桃精品| 亚洲精品1区| 欧美亚洲免费| 欧美国产高清| 国产欧美日韩三级| 亚洲毛片一区| 欧美伊人久久大香线蕉综合69| 久热爱精品视频线路一| 99国产一区| 久久久亚洲午夜电影| 欧美午夜片欧美片在线观看| 精品白丝av| 亚洲欧美日韩区| 欧美电影在线免费观看网站 | 久久午夜视频| 亚洲精品中文字幕有码专区| 午夜性色一区二区三区免费视频| 欧美成人精品影院| 国产原创一区二区| 中文网丁香综合网| 欧美福利一区| 欧美一区二区| 国产精品久久77777| 亚洲精选中文字幕| 免费日韩视频| 先锋a资源在线看亚洲| 国产精品对白刺激久久久| 亚洲国产综合在线看不卡| 久久国产福利国产秒拍| 宅男精品导航|