強連通演算法

❶ 請問數據結構中圖的強連通分量是什麼能具體解釋一下嗎

有向圖的極大強連通子圖，稱為強連通分量(strongly connected components)。

在有向圖G中，如果兩個頂點vi,vj間（vi>vj）有一條從vi到vj的有向路徑，同時還有一條從vj到vi的有向路徑，則稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。

(1)強連通演算法擴展閱讀：

強連通分量Tarjan演算法

任何一個強連通分量，必定是對原圖的深度優先搜索樹的子樹。那麼只要確定每個強連通分量的子樹的根，然後根據這些根從樹的最低層開始，一個一個的拿出強連通分量即可。

維護兩個數組，一個是indx[1..n]，一個是mlik[1..n]，其中indx[i]表示頂點i開始訪問時間，mlik[i]為與頂點i鄰接的頂點未刪除頂點j的mlik[j]和mlik[i]的最小值(mlik[i]初始化為indx[i])。這樣，在一次深搜的回溯過程中，如果發現mlik[i]==indx[i]那麼，當前頂點就是一個強連通分量的根。

因為如果它不是強連通分量的根，那麼它一定是屬於另一個強連通分量，而且它的根是當前頂點的祖宗，那麼存在包含當前頂點的到其祖宗的迴路，可知mlik[i]一定被更改為一個比indx[i]更小的值。

至於拿出強連通分量，如果當前節點為一個強連通分量的根，那麼它的強連通分量一定是以該根為根節點的(剩下節點)子樹。在深度優先遍歷的時候維護一個堆棧，每次訪問一個新節點，就壓入堆棧。

這樣，由於當前節點是這個強連通分量中最先被壓入堆棧的，那麼在當前節點以後壓入堆棧的並且仍在堆棧中的節點都屬於這個強連通分量。

可以用反證法證明這個做法的正確性。假設一個節點在當前節點壓入堆棧以後壓入並且還存在，同時它不屬於該強連通分量，那麼它一定屬於另一個強連通分量，但當前節點是它的根的祖宗，那麼這個強連通分量應該在此之前已經被拿出。

❷ 怎麼用c語言和數據結構來編寫一個判斷有向圖是否為強連通圖的演算法

強連通圖表明任意兩點之間可以互相到達。
方案1：判斷結點A可以到達的點的方法如下：
首先SA = {A}；
while 1
取SA中任意沒有被去過的點x，根據以x為起點的有向線段，判斷x可以直接到達的點，然後這些點加入SA；
如此循環，直到SA中的點的個數沒有變化了
end
這樣得到的集合SA是所有A可以到達的點的一個集合。
判斷SA 是否等於S，若不等於S，表明不是強連通。

如此循環，求出所有S中的點的能夠到達的點集。如果所有的點集都等於S表明強連通圖。

方案2：可以優化1

❸ 對pagerank演算法的整理

1、首先先大致介紹下pagerank，pagerank是Google排名演算法法則的一部分，是用來標記網頁的等級的一種方法，也是用來衡量一個網頁好壞的唯一標准。pagerank他採用PR值來劃分網頁的受歡迎度，PR值越高，則表名受歡迎度越高，PR最高為10，最低為0，一般PR達到4，則表名網站已經不錯了。PR為4的網站比PR為3的網站不是單純的好一點來形容，他是一種里氏震級的形式來形容的，就好比地震的等級，是指數刻度增長的，因此可以想像PR為10的網站是一種什麼程度。因為這個演算法是Google提出的，因此Google將自己的網站PR值設置為10，所以想要自己的網站PR達到10，是非常難的，如果你的網站可以達到Google的水平。

2、介紹完了pagerank是一個什麼東西後，我們就來介紹一下pagerank如何計算的。

2.1、用個例子來說明下PageRank演算法

在網頁A中有B、C、D三個鏈接，在網頁B中有A、C兩個個鏈接，在網頁C中有D鏈接，網頁D中有A、B兩個鏈接。（可以看出這個圖是強鏈接的，任何一個節點都可以到達另一個節點）。

我們假設每一個鏈接訪問的概率是相同的，為了計算方便我們將每一個網頁的PageRank設置為1。

先給出計算公式

PR(pj) 表示網頁 pj 的 PageRank 得分，L(pj) 表示網頁 pj 的出鏈接數量，1/L(pj) 就表示從網頁 pj 跳轉到 pi 的概率。

所以我們來計算第一次迭代後的PR值：

PR(A)=PR(B)/2+PR(D)/2

PR(B)=PR(A)/3+PR(D)/2

PR(C)=PR(A)/3+PR(B)/2

PR(D)=PR(A)/3+PR(C)/1

PR(A)+PR(B)+PR(C)+PR(D)=1

PR(A)=0.265, PR(B)=0.235, PR(C)=0.206, PR(D)=0.294

通過上面的公式在不斷的進行迭代，可以得到一個收斂值，大概是在（0.265，0.235，2.206，0.294）附近。

2.2看完公式之後，我們來考慮倆種特殊的情況

2.2.1終止問題

上面過程要滿足收斂性，需要具備一個條件：圖是強連通的，即從任意網頁可以到達其他任意網頁。

互聯網中存在網頁不滿足強連通的特性，因為有一些網頁不指向任何網頁，按照上面公式迭代計算下去，導致前面累計得到的轉移概率被清零，最終得到的概率分布向量所有元素幾乎都為0。

假設把上面圖中C到D的鏈接丟掉，C變成了一個終止點，得到下面這個圖：

轉移矩陣M為：

不斷迭代，最終得到所有元素都為0。

2.2.2 、陷阱問題

陷阱問題：是指有些網頁不存在指向其他網頁的鏈接，但存在指向自己的鏈接。比如下面這個圖：

這種情況下，PageRank演算法不斷迭代會導致概率分布值全部轉移到c網頁上，這使得其他網頁的概率分布值為0，從而整個網頁排名就失去了意義。如果按照上面圖則對應的轉移矩陣M為：

不斷迭代，最終得倒如下結果：

為了解決終止點問題和陷阱問題 ，下面需要對演算法進行改進。假設選取下一個跳轉頁面時，既不選 當前頁面 ，也不選 當前網頁上的其他鏈接 ，而是以一定概率跳轉到其他不相關網頁，那麼上面兩個問題就能得到很好的解決，這就是 完整 PageRank 演算法思想 。

N表示的時網頁鏈接的個數，α表示不進行隨機跳轉的概率。

利用上面公式繼續迭代下去，直到收斂，得到最終rank值。

PageRank 的計算是采樣迭代法實現的：一開始所有網頁結點的初始 PageRank 值都可以設置為某個相同的數，例如 1，然後我們通過上面這個公式，得到每個結點新的 PageRank 值。每當一張網頁的 PageRank 發生了改變，它也會影響它的出鏈接所指向的網頁，因此我們可以再次使用這個公式，循環地修正每個網頁結點的值。由於這是一個馬爾科夫過程，所以我們能從理論上證明，所有網頁的 PageRank 最終會達到一個穩定的數值。整個證明過程很復雜，這里我們只需要知道這個迭代計算的過程就行了。

3、基於本文主題叫做數學建模之美，也是一篇讀後感，所以我們還是寫一下感受吧。

這個演算法的優美之處，就在於巧妙地將網頁內容的好壞，根據鏈接數的形式，用PR值進行了排名，它不僅激發網頁越做越好，也促進了各個網頁之間的聯系。

同時在結構方面，他將一個復雜的問題，進行了簡單的類比，用圖結構的形式代替鏈接的形式，用戶訪問的順序，也就是節點的走向。所以數學之美就在於他是非常的簡單，用簡單的原理，向我們展示了一個復雜的問題。