圖論演演算法

第一節 基本概念

一、什麼是圖？ 　　

很簡單，點用邊連起來就叫做圖，嚴格意義上講，圖是一種資料結構，定義為：graph=（V，E）。V是一個非空有限集合，代表頂點（結點），E代表邊的集合。

二、圖的一些定義和概念

(a)有向圖：圖的邊有方向，只能按箭頭方向從一點到另一點。(a)就是一個有向圖。 (b)無向圖：圖的邊沒有方向，可以雙向。(b)就是一個無向圖。

結點的度：無向圖中與結點相連的邊的數目，稱為結點的度。 結點的入度：在有向圖中，以這個結點為終點的有向邊的數目。

結點的出度：在有向圖中，以這個結點為起點的有向邊的數目。

權值：邊的「費用」，可以形象地理解為邊的長度。

連通：如果圖中結點U，V之間存在一條從U通過若干條邊、點到達V的通路，則稱U、V 是連通的。

迴路：起點和終點相同的路徑，稱為迴路，或「環」。

完全圖：一個n 階的完全無向圖含有n*(n-1)/2 條邊；一個n 階的完全有向圖含有n*(n-1)條邊； 　　　

稠密圖：一個邊數接近完全圖的圖。 　　　　

稀疏圖：一個邊數遠遠少於完全圖的圖。 　　　　

強連通分量：有向圖中任意兩點都連通的最大子圖。右圖中，1-2-5構成一個強連通分量。特殊地，單個點也算一個強連通分量，所以右圖有三個強連通分量：1-2-5，4，3。

三、圖的儲存結構

1.二維陣列鄰接矩陣儲存

定義int G[101][101]; G[i][j]的值，表示從點i到點j的邊的權值，定義如下：

建立鄰接矩陣時，有兩個小技巧: 　

　初始化陣列大可不必使用兩重for迴圈。 　　

1)　　如果是int陣列，採用memset(g, 0x7f, sizeof(g))可全部初始化為一個很大的數(略小於0x7fffffff)，使用memset(g, 0, sizeof(g))，全部清為0，使用memset(g, 0xaf, sizeof(g))，全部初始化為一個很小的數。　　

2)如果是double陣列，採用memset(g,127,sizeof(g));可全部初始化為一個很大的數1.38*10306，使用memset(g, 0, sizeof(g))全部清為0.

下面是建立圖的鄰接矩陣的參考程式段：

#include<iostream>                                                                                             
using namespace std;
int i,j,k,e,n;
double g[101][101];
double w;
int main()
{
    int i,j;
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        g[i][j] = 0x7fffffff（賦一個超大值）;  //初始化，對於不帶權的圖g[i][j]=0，表示沒有邊連通。這裡用0x7fffffff代替無窮大。
    cin >> e;
    for (k = 1; k <= e; k++)
    {
         cin >> i >> j >> w;             //讀入兩個頂點序號及權值
         g[i][j] = w;                    //對於不帶權的圖g[i][j]=1
         g[j][i] = w;                    //無向圖的對稱性,如果是有向圖則不要有這句！
    } 
    …………
    return 0;
}

2.陣列模擬鄰接表儲存 　　

圖的鄰接表儲存法，又叫鏈式儲存法。本來是要採用連結串列實現的，但大多數情況下只要用陣列模擬即可。 　　

以下是用陣列模擬鄰接表儲存的參考程式段：

#include <iostream>
using namespace std;
const int maxn=1001,maxm=100001;
struct Edge
{
    int next;                               //下一條邊的編號 
    int to;                                 //這條邊到達的點 
    int dis;                                //這條邊的長度 
}edge[maxm];

int head[maxn],num_edge,n,m,u,v,d;

void add_edge(int from,int to,int dis)      //加入一條從from到to距離為dis的單向邊 
{
    edge[++num_edge].next=head[from];
    edge[num_edge].to=to;
    edge[num_edge].dis=dis;
    head[from]=num_edge;
}
int main()
{
    num_edge=0;
    scanf("%d %d",&n,&m);                    //讀入點數和邊數
    for(int i=1;i<=m;i++)
    {
          scanf("%d %d %d",&u,&v,&d);   //u、v之間有一條長度為d的邊 
          add_edge(u,v,d);
    }
    for(int i=head[1];i!=0;i=edge[i].next)   //遍歷從點1開始的所有邊 
    {
           //...
    }

    //...

    return 0;
}

兩種方法各有用武之地，需按具體情況，具體選用。

第二節 圖的遍歷

一、深度優先與廣度優先遍歷 　　

從圖中某一頂點出發系統地存取圖中所有頂點，使每個頂點恰好被存取一次，這種運算操作被稱為圖的遍歷。

為了避免重複存取某個頂點，可以設一個標誌陣列visited[i]，未存取時值為false，存取一次後就改為true。 　　

圖的遍歷分為深度優先遍歷和廣度優先遍歷兩種方法，兩者的時間效率都是O(n*n)。

1.深度優先遍歷 　　

深度優先遍歷與深搜DFS相似，從一個點A出發，將這個點標為已存取visited[i]:=true;，然後再存取所有與之相連，且未被存取過的點。

當A的所有鄰接點都被存取過後，再退回到A的上一個點（假設是B），再從B的另一個未被存取的鄰接點出發，繼續遍歷。 　　

例如對右邊的這個無向圖深度優先遍歷，假定先從1出發 　　程式以如下順序遍歷： 　　1→2→5，然後退回到2，退回到1。 　　

從1開始再存取未被存取過的點3 ，3沒有未存取的鄰接點，退回1。 　　

再從1開始存取未被存取過的點4，再退回1 。 　　

起點1的所有鄰接點都已存取，遍歷結束。

2.廣度優先遍歷 　　

廣度優先遍歷並不常用，從程式設計複雜度的角度考慮，通常採用的是深度優先遍歷。 　　

廣度優先遍歷和廣搜BFS相似，因此使用廣度優先遍歷一張圖並不需要掌握什麼新的知識，在原有的廣度優先搜尋的基礎上，做一點小小的修改，就成了廣度優先遍歷演演算法。

二、一筆畫問題 　　

如果一個圖存在一筆畫，則一筆畫的路徑叫做尤拉路，如果最後又回到起點，那這個路徑叫做歐拉回路。 　　

我們定義奇點是指跟這個點相連的邊數目有奇數個的點。對於能夠一筆畫的圖，我們有以下兩個定理。 　　　

定理1：存在尤拉路的條件：圖是連通的，有且只有2個奇點。 　　　

定理2：存在歐拉回路的條件：圖是連通的，有0個奇點。 　　

兩個定理的正確性是顯而易見的，既然每條邊都要經過一次，那麼對於尤拉路，除了起點和終點外，每個點如果進入了一次，顯然一定要出去一次，顯然是偶點。對於歐拉回路，每個點進入和出去次數一定都是相等的，顯然沒有奇點。 　

求尤拉路的演演算法很簡單，使用深度優先遍歷即可。 　　

根據一筆畫的兩個定理，如果尋找歐拉回路，對任意一個點執行深度優先遍歷；找尤拉路，則對一個奇點執行DFS，時間複雜度為O(m+n)，m為邊數，n是點數。

以下是尋找一個圖的尤拉路的演演算法實現：

樣例輸入:第一行n，m，有n個點，m條邊，以下m行描述每條邊連線的兩點。

5 5

1 2

2 3

3 4

4 5

5 1

樣例輸出:尤拉路或歐拉回路

1 5 4 3 2 1

#include<iostream>
#include<cstring>
using namespace std;
#define maxn 101
int g[maxn][maxn];               //此圖用鄰接矩陣儲存
int du[maxn];                    //記錄每個點的度，就是相連的邊的數目
int circuit[maxn];               //用來記錄找到的尤拉路的路徑
int n,e,circuitpos,i,j,x,y,start;
void find_circuit(int i){         //這個點深度優先遍歷過程尋找尤拉路
　 int j;
　 for (j = 1; j <= n; j++)
      if (g[i][j] == 1)          //從任意一個與它相連的點出發
　　   {
　　        g[j][i] = g[i][j] = 0; 
　　        find_circuit(j);
　　    } 
　　circuit[++circuitpos] = i;   //記錄下路徑
}
int main()
　　{
　　    memset(g,0,sizeof(g));
　　    cin >> n >> e;
　　    for (i = 1; i <= e; i++)
　　    {
　　        cin >> x >> y;
　　        g[y][x] = g[x][y] = 1;
　　        du[x]++;                    //統計每個點的度
　　        du[y]++;
　　    }
　　    start = 1;                      //如果有奇點，就從奇點開始尋找，這樣找到的就是
　　    for (i = 1; i <= n; i++)        //尤拉路。沒有奇點就從任意點開始，
　　       if (du[i]%2 == 1)            //這樣找到的就是歐拉回路。(因為每一個點都是偶點)
              start = i;
　　    circuitpos = 0;
　　    find_circuit(start);
　　    for (i = 1; i <= circuitpos; i++)
　　        cout << circuit[i] << ' ';
　　    cout << endl;
　　    return 0;
}

注意以上程式具有一定的侷限性，對於下面這種情況它不能很好地處理：

上圖具有多個歐拉回路，而本程式只能找到一個迴路。讀者在遇到具體問題時，還應對程式作出相應的修改。

第三節  最短路徑演演算法

如下圖所示，我們把邊帶有權值的圖稱為帶權圖。邊的權值可以理解為兩點之間的距離。一張圖中任意兩點間會有不同的路徑相連。最短路徑就是指連線兩點的這些路徑中最短的一條。 　　

　我們有四種演演算法可以有效地解決最短路徑問題。有一點需要讀者特別注意：邊的權值可以為負。當出現負邊權時，有些演演算法不適用。

一、求出最短路徑的長度 　　

以下沒有特別說明的話，dis[u][v]表示從u到v最短路徑長度，w[u][v]表示連線u，v的邊的長度。 1.Floyed-Warshall演演算法 O(N3) 　　

簡稱Floyed(弗洛伊德)演演算法，是最簡單的最短路徑演演算法，可以計算圖中任意兩點間的最短路徑。Floyed的時間複雜度是O (N3)，適用於出現負邊權的情況。 演演算法描述： 初始化：點u、v如果有邊相連，則dis[u][v]=w[u][v]。 　　

如果不相連則dis[u][v]=0x7fffffff For (k = 1; k <= n; k++) For (i = 1; i <= n; i++) For (j = 1; j <= n; j++) If (dis[i][j] >dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j]; 演演算法結束：dis[i][j]得出的就是從i到j的最短路徑。

演演算法分析&思想講解： 　　三層迴圈，第一層迴圈中間點k，第二第三層迴圈起點終點i、j，演演算法的思想很容易理解：如果點i到點k的距離加上點k到點j的距離小於原先點i到點j的距離，那麼就用這個更短的路徑長度來更新原先點i到點j的距離。 　　在上圖中，因為dis[1][3]+dis[3][2]<dis[1][2]，所以就用dis[1][3]+dis[3][2]來更新原先1到2的距離。 　　我們在初始化時，把不相連的點之間的距離設為一個很大的數，不妨可以看作這兩點相隔很遠很遠，如果兩者之間有最短路徑的話，就會更新成最短路徑的長度。Floyed演演算法的時間複雜度是O(N3)。

第四節 圖的連通性問題

一、判斷圖中的兩點是否連通

1、Floyed演演算法 　　　

時間複雜度：O(N3 )

演演算法實現： 　　把相連的兩點間的距離設為dis[i][j]=true,不相連的兩點設為dis[i][j]=false，用Floyed演演算法的變形： 　

for (k = 1; k <= n; k++)

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++) 　

dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]); 　　

最後如果dis[i][j]=true的話，那麼就說明兩點之間有路徑連通。 　

2、遍歷演演算法 　　

時間複雜度：O(N2 )

演演算法實現： 　　從任意一個頂點出發，進行一次遍歷，能夠從這個點出發到達的點就與起點是聯通的。

這樣就可以求出此頂點和其它各個頂點的連通情況。

所以只要把每個頂點作為出發點都進行一次遍歷，就能知道任意兩個頂點之間是否有路存在。 　　

可以使用DFS實現。 　　

有向圖與無向圖都適用。

二、求有向圖的強連通分量

Kosaraju演演算法可以求出有向圖中的強連通分量個數，並且對分屬於不同強連通分量的點進行標記。

它的演演算法描述較為簡單： (1) 第一次對圖G進行DFS遍歷，並在遍歷過程中，記錄每一個點的退出順序。以下圖為例：

如果以1為起點遍歷，存取結點的順序如下：

結點第二次被存取即為退出之時，那麼我們可以得到結點的退出順序：

(2)倒轉每一條邊的方向，構造出一個反圖G’。

然後按照退出順序的逆序對反圖進行第二次DFS遍歷。我們按1、4、2、3、5的逆序第二次DFS遍歷：

存取過程如下：

每次遍歷得到的那些點即屬於同一個強連通分量。

1、4屬於同一個強連通分量，2、3、5屬於另一個強連通分量。