資料結構與算法：圖

圖論是計算機研究的一個重要分支，有關圖論的内容可以寫很多，但正是因為圖論的這種複雜性，在程式員面試筆試中，有關圖論的問題并不多見，考察的也并不深奧。本節内容涉及一些經常出現的圖論問題，并給予詳細的解答。

• 拓撲排序
• DFS BFS
  • DFS
  • BFS
• 關鍵路徑
• 最短路徑

拓撲排序

從數學的角度來講，拓撲排序就是由任意集合上的一個偏序關系得到一個該集合的全序關系的操作。如果将某一集合中的所有元素作為圖的結點，将該集合上的偏序關系作為圖的邊，則任意一個偏序關系即可以表示一個有向圖。

拓撲排序是有向圖的一個重要操作。在給定的有向圖G中，若頂點序列V1，v2，…, vn 滿足下列條件：若在有向圖G總從頂點vi到vj有一條路徑，則在序列中頂點vi必在頂點vj之前，便稱這個序列為一個拓撲序列。求一個又相遇拓撲序列的過程稱為拓撲排序。

一個圖的拓撲排序可以看成是圖中所有頂點沿水準線排列而成的一個序列，使得所有的有向邊均從左指向右。在很多應用中，有向無環圖用于說明事件發生的先後次序。

常用的拓撲排序方法如下：

（1）從有向圖中選擇一個沒有前驅（即入度為0）的頂點并且輸出它。

（2）從圖中删去該頂點，并且删去從該頂點發出的所有邊。

（3）重複上述步驟（1）和步驟（2），直到目前有向圖中不存在沒有前驅結點的頂點為止，或者目前有向圖中的所有結點均已輸出為止。

需要注意的是，一個有向無環圖的拓撲排序序列不是唯一的。

例如，對于圖13-20而言，進行拓撲排序會得到兩個序列： { v1,v2,v5,v4,v3,v7,v6 } 或者 { v1,v2,v5,v4,v7,v3,v6 }

從拓撲排序的算法可知，如果AOV網絡有n個頂點，e條邊，在拓撲排序的過程中，搜尋入度為零的頂點，建立頂點棧所需要的時間是O(n)。在正常情況下，有向圖有n個頂點，每個頂點進一次棧，出一次棧，共輸出n次。頂點入度減1的運算共執行了e次。是以，拓撲排序總的時間複雜度為O(n+e)。

DFS? BFS

最常見的圖的周遊方式有深度優先周遊（Depth First Search，DFS）與廣度優先周遊（Breadth First Search， BFS）兩種。圖的深度優先算法類似于樹的先根周遊，圖的廣度優先算法類似于樹的層次周遊。

DFS

DFS是從每一個頂點開始的深度優先周遊，結果都是對該分支路徑深入周遊到不能再深入為止，且每個頂點隻能被通路一次。具體實作過程為從圖G中某個頂點v觸發，先通路該結點，然後一次沿着未被通路過的v的鄰接頂點進行深度優先周遊，直到圖G中和頂點v之間有相連路徑的其他頂點都被通路過為止。此時，如果圖G中還有其他頂點未被通路過，則從這些頂點中任選一個作為起始頂點，重複上述過程，直到圖G中的所有頂點都被通路過為止。

深度優先搜尋算法的具體實作代碼如下：

int visited[N]; //數組 visited[]表示圖中頂點的通路情況，1表示已通路，0表示未通路
void DFS( Graph G, int v )
{
    visited[v] = ;
    Visit(v); //表示對頂點v的通路

    //函數FirstAdjVex( G,v ) 傳回圖G中v的第一個鄰接點
    //函數NextAdjVex( G,v,w )傳回圖G中v的（相對于w）的下一個鄰接頂點，若w是v的最後一個鄰接點，則傳回空
    for(w=FirstAdjVex(G,v);w>=;w=NextAdjVex(G,v,w))
    {
        if(!visited[w])
            DFS(G,w); //對v的未被通路過的鄰接頂點進行深度優先搜尋
    }
}
void DFSSearch( Graph G )//對圖G進行深度優先搜尋
{
    for(v=;v<G.vexnum; ++v)
        visited[v] = ;
    for( v=;v<G.vexnum; ++v)
        if(!visited[v])
            DFS(G,v); //對未被通路過的頂點調用DFS
}
           

BFS

BFS也稱為寬度優先算法，屬于一種盲目搜尋方法，是很重要的圖算法的原型。其目的是逐層搜尋圖中的所有頂點，且保證圖中的所有頂點隻被通路過一次。

具體過程如下：在給定圖G=（V,E）中，從圖G中的某個頂點v出發，通路該頂點後，依次通路所有未被通路過的v的鄰接頂點，然後再沿着這些頂點出發，依次通路它們未被通路過的鄰接頂點，并且保證先被通路頂點的鄰接頂點先于後被通路頂點的鄰接頂點而被通路。所有與頂點v有相通路徑的頂點都被通路結束後，如果圖G中還有其他頂點未被通路過，則從這些頂點中任選一個頂點作為起始頂點，重複上述過程，直到圖G中的所有頂點都被通路過為止。

廣度優先搜尋算法的具體實作代碼如下：

int visited[N];//表示頂點的通路情況，1表示已通路，0表示未通路
void BFSSearch( Graph G )
{
    for(v=; v<G.vexnum; ++v )
        visited[v] = ;
    InitQueue( Q ) //初始化隊列
    for( v=; v<G.vexnum; ++v )
        if( !visited[v])
        {
            visited[v] = ;
            Visit( v );
            EnQueue( Q,v );
            while( !QueueEmpty(Q) )
            {
                Dequeue( Q,u ); //出隊
                for( w=FirstAdjVex(G,u); w>=; w=NextAdjVex(G,u,w) ) 
                    if(!visited[w])
                    {
                        visited[w] = ;
                        Visit(w);
                        EnQueue(Q,w);
                    }

            }
        }
}
           

關鍵路徑

關鍵路徑是指一個圖（AOE）中長度最長（路徑上的各個活動所持續的時間之和）的路徑。

用e(k)表示活動（即弧）k的最早開始時間

用l(k)表示活動k的最晚開始時間，則把e(k) = l(k)的活動叫做關鍵活動。關鍵路徑上的所有活動都為關鍵活動。

由于AOE網中的某些活動能夠同時進行，故完成整個工程所必須花費的時間應該為始點到終點的最大路徑長度。關鍵路徑長度是整個工程所需的最短工期。

用ve(i)表示事件（即頂點）i的最早開始時間，vl(i)表示事件i的最晚開始時間。如果活動k由弧

<m,n>

表示，用dut表示該活動的持續時間，則有：

e(k) = ve(m)
l(k)=vl(n)-dut(<m,n>)
           

求解關鍵路徑的具體算法如下（假設圖中共有n個頂點）：

（1）從開始頂點v0出發，假設ve(0)=0，然後按照拓撲有序求出其他各頂點i的最早開始時間ve(i)，如果得到的拓撲序列中頂點數目小于圖中的頂點數，則表示圖中存在回路，算法結束，否則繼續執行。

（2）從結束頂點vn出發，假設v1(n-1)=ve(n-1)，然後按拓撲有序求出其他各頂點i的最晚發生時間vl(i)

（3）根據各頂點的最早開始時間ve(i)和最晚開始時間vl(i)依次求出每條弧的最早開始時間e(k)和最晚開始時間l(k)，如果有e(k)=l(k),則為關鍵活動。關鍵活動組成的路徑則為關鍵路徑。

最短路徑

Dijkstra算法原理是對于源頂點v0，首先選擇其直接相鄰的頂點中長度最短的頂點vi，那麼根據已知可得，由v0經過vi到達與vi直接相鄰的頂點vj的最短距離dist[j]為matrix[v0][j]與dist[i]+matrix[i][j]中的最小值，即dist[j]=min{ matrix[v0][j], dist[i]+matrix[i][j]}

該算法的實作過程如下（S是已求得最短路徑的終點集合，V是所有結點集合）

（1）V-S = 未确定最短路徑的頂點的集合，初始時 S={A}，兩個結點之間沒有邊時表示這兩點之間的路徑長度為無限大

（2）下一條路徑的計算方式：首先，求出A到Vi中間隻經S中頂點的最短路徑，其中，Vi 屬于 V-S。然後，将上述的到最短路徑與源點A到結點Vi的路徑長度進行比較，長度最小者即為源點A到結點Vi的最短路徑。最後将所求最短路徑的終點（即Vi）加入S中

（3）重複步驟（2），直到求出所有終點的最短路徑，即S中的結點數量與V中的結點數量相等。

Dijkstra算法的時間複雜度為O(n^2)，空間複雜度取決于存儲方式，鄰接矩陣為O(n^2)

除了Dijkstra算法外，Bellman-Ford算法也是一種常見的求解單源最短路徑問題的算法。與Dijkstra算法不同的是，在Bellman-Ford算法中，邊的權值可以為負數，它的時效性比較好，時間複雜度為O(VE)