• <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>

            O(1) 的小樂

            Job Hunting

            公告

            記錄我的生活和工作。。。
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            統(tǒng)計

            • 隨筆 - 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搜索的時候的入隊序列,Each time that depth-first search finishes expanding a vertex u, push u onto S.只有當(dāng)擴(kuò)展結(jié)束了此節(jié)點之后,此節(jié)點才會被push onto S.

            算法思路:

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

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

            證明是很簡單的:

            假設(shè)以上算法從u訪問到了v,那么說明反向圖有一條從u到v的邊,也就說明了原圖中有一條從v到u的邊,又因為u的標(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];                 //時間戳對應(yīng)的點
            int timestamp;               //時間戳
            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確定時間戳
                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--) {//按時間戳從大到小搜
                    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;
            }

             

             

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

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

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

             

            Reference :

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

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

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

            評論

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

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

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


            中文精品久久久久人妻不卡| 少妇内射兰兰久久| 狠狠色伊人久久精品综合网| 99久久er这里只有精品18| 青青青青久久精品国产| 麻豆久久| 久久精品天天中文字幕人妻| 国产一区二区精品久久 | 国产精品熟女福利久久AV| 久久99亚洲综合精品首页| 亚洲一区精品伊人久久伊人| 久久久久免费看成人影片| 国产日韩久久久精品影院首页| 2021国内久久精品| 91精品国产91久久久久久青草| 欧美大战日韩91综合一区婷婷久久青草| 久久亚洲熟女cc98cm| 99久久精品国产综合一区| 777午夜精品久久av蜜臀| 国产亚洲精午夜久久久久久| 亚洲午夜久久久久妓女影院 | 久久av免费天堂小草播放| 久久久久99这里有精品10| 91精品国产综合久久婷婷| 少妇人妻综合久久中文字幕| 亚洲国产二区三区久久| 久久亚洲国产成人精品性色| 日日狠狠久久偷偷色综合96蜜桃 | 亚洲AV日韩精品久久久久久| 99久久国产亚洲高清观看2024| 青青草原精品99久久精品66| 久久久久99精品成人片牛牛影视| 91精品国产91久久综合| 亚洲AV无码久久精品狠狠爱浪潮| 一级做a爰片久久毛片看看| 久久久WWW成人| 精品久久国产一区二区三区香蕉| 久久国产精品久久| 久久综合狠狠综合久久激情 | 国产美女久久精品香蕉69| 久久ZYZ资源站无码中文动漫|