2.8　圖結構

圖（Graph）結構也是一種非線性數據結構，圖結構在實際生活中具有豐富的例子。例如，通信網絡、交通網絡、人際關系網絡等都可以歸結為圖結構。圖結構的組織形式要比樹結構更為復雜，因此，圖結構對存儲和遍歷等操作具有更高的要求。

2.8.1　什么是圖結構

前面介紹的樹結構的一個基本特點是數據元素之間具有層次關系，每一層的元素可以和多個下層元素關聯，但是只能和一個上層元素關聯。如果將此規則進一步擴展，也就是說，每個數據元素之間可以任意關聯，這就構成了一個圖結構。正是這種任意關聯性導致了圖結構中數據關系的復雜性。研究圖結構的一個專門理論工具便是圖論。

典型的圖結構，如圖2-26所示。一個典型的圖結構包括如下內容。

?頂點（Vertex）：圖中的數據元素。

?邊（Edge）：圖中連接這些頂點的線。

所有的頂點構成一個頂點集合，所有的邊構成邊集合，一個完整的圖結構由頂點集合和邊集合組成。圖結構在數學上一般記為以下形式：

G=（V，E）

或者

G=（V（G），E（G））

其中，V（G）表示圖結構中所有頂點的集合，頂點可以用不同的數字或者字母來表示。E（G）是圖結構中所有邊的集合，每條邊由所連接的兩個頂點表示。

注意：圖結構中頂點集合V（G）必須為非空，即必須包含一個頂點。而圖結構中邊集合E（G）可以為空，此時表示沒有邊。

例如，對于圖2-26所示的圖結構，其頂點集合和邊集合如下：

V（G）={V1，V2，V3，V4，V5，V6}

E（G）={（V1，V2），（V1，V3），（V1，V5），（V2，V4），（V3，V5），（V4，V5），（V4，V6），（V5，V6）}

2.8.2　圖的基本概念

圖論是專門研究圖結構的一個理論工具。為了講解和讀者理解的方便，這里簡單介紹一些基本的圖結構概念。

1）無向圖

如果一個圖結構中，所有的邊都沒有方向性，那么這種圖便稱為無向圖。典型的無向圖，如圖2-27所示。由于無向圖中的邊沒有方向性，這樣，在表示邊的時候對兩個頂點的順序沒有要求。例如，頂點V1和頂點V5之間的邊，可以表示為（V1，V5），也可以表示為（V5，V1）。

對于圖2-27所示的無向圖，對應的頂點集合和邊集合如下：

V（G）={V1，V2，V3，V4，V5}

E（G）={（V1，V2），（V1，V5），（V2，V4），（V3，V5），（V4，V5），（V1，V3）}

2）有向圖

如果一個圖結構中，邊有方向性，那么這種圖便稱為有向圖。典型的有向圖，如圖2-28所示。由于有向圖中的邊有方向性，這樣，在表示邊的時候對兩個頂點的順序有要求。并且，為了同無向圖區分，采用尖括號表示有向邊。例如，<V3，V4>表示從頂點V3到頂點V4的一條邊，而<V4，V3>表示從頂點V4到頂點V3的一條邊。<V3，V4>和<V4，V3>表示的是兩條不同的邊。

對于圖2-28所示的有向圖，對應的頂點集合和邊集合如下：

V（G）={V1，V2，V3，V4，V5，V6}

E（G）={<V1，V2>，<V2，V1>，<V2，V3>，<V3，V4>，<V4，V3>，<V4，V5>，<V5，V6>，<V6，V4>，<V6，V2>}

3）頂點的度（Degree）

連接頂點的邊的數量稱為該頂點的度。頂點的度在有向圖和無向圖中具有不同的表示。對于無向圖，一個頂點V的度比較簡單，其是連接該頂點的邊的數量，記為D（V）。例如，在圖2-27所示的無向圖中，頂點V4的度為2，而V5的度為3。

對于有向圖要稍復雜些，根據連接頂點V的邊的方向性，一個頂點的度有入度和出度之分。

?入度是以該頂點為端點的入邊數量，記為ID（V）。

?出度是以該頂點為端點的出邊數量，記為OD（V）。

因此，有向圖中，一個頂點V的總度便是入度和出度之和，即D（V）=ID（V）+OD（V）。例如，在圖2-28所示的有向圖中，頂點V3的入度為2，出度為1，因此，頂點V3的總度為3。

4）鄰接頂點

鄰接頂點是指圖結構中一條邊的兩個頂點。鄰接頂點在有向圖和無向圖中具有不同的表示。對于無向圖，鄰接頂點比較簡單。例如，在圖2-27所示的無向圖中，頂點V1和頂點V5互為鄰接頂點，頂點V2和頂點V4互為鄰接頂點等。另外，頂點V1的鄰接頂點有頂點V2、頂點V3和頂點V5。

對于有向圖要稍復雜些，根據連接頂點V的邊的方向性，兩個頂點分別稱為起始頂點（起點或始點）和結束頂點（終點）。有向圖的鄰接頂點分為如下兩類。

?入邊鄰接頂點：連接該頂點的邊中的起始頂點。例如，對于組成<V1，V2>這條邊的兩個頂點，V1是V2的入邊鄰接頂點。

?出邊鄰接頂點：連接該頂點的邊中的結束頂點。例如，對于組成<V1，V2>這條邊的兩個頂點，V2是V1的出邊鄰接頂點。

5）無向完全圖

如果在一個無向圖中，每兩個頂點之間都存在一條邊，那么這種圖結構稱為無向完全圖。典型的無向完全圖，如圖2-29所示。

理論上可以證明，對于一個包含N個頂點的無向完全圖，其總的邊數為N（N-1）/2。

6）有向完全圖

如果在一個有向圖中，每兩個頂點之間都存在方向相反的兩條邊，那么這種圖結構稱為有向完全圖。典型的有向完全圖，如圖2-30所示。

理論上可以證明，對于一個包含N個頂點的有向完全圖，其總的邊數為N（N-1），無向完全圖的兩倍。

7）子圖

子圖的概念類似子集合，由于一個完整的圖結構包括頂點和邊，因此，一個子圖的頂點和邊都應該是另一個圖結構的子集合。例如，圖2-31中，圖（a）為一個無向圖結構，圖（b）、圖（c）和圖（d）均為圖（a）的子圖。

這里需要強調的是，只有頂點集合是子集的，或者只有邊集合是子集的，都不是子圖。

8）路徑

路徑即圖結構中兩個頂點之間的連線，路徑上邊的數量稱為路徑長度。兩個頂點之間的路徑可能途經多個其他頂點，兩個頂點之間的路徑也可能不止一條，相應的路徑長度可能不一樣。

圖結構中的一條路徑，如圖2-32所示。這里粗線部分顯示了頂點V5到V2之間的一條路徑，這條路徑途經的頂點為V4，途經的邊依次為（V5，V4）、（V4，V2），路徑長度為2。

同樣，還可以在該圖中找到頂點V5到V2之間的其他路徑，分別為：

?路徑（V5，V1）、（V1，V2），途經頂點V1，路徑長度為2。

?路徑（V5，V3）、（V3，V1）、（V1，V2），途經頂點V1和V3，路徑長度為3。

圖結構中的路徑還可以細分為如下三種形式。

?簡單路徑：在圖結構中，如果一條路徑上頂點不重復出現，則稱為簡單路徑。

?環：在圖結構中，如果路徑的第一個頂點和最后一個頂點相同，則稱之為環，有時也稱為回路。

?簡單回路：在圖結構中，如果除第一個頂點和最后一個頂點相同，其余各頂點都不重復的回路稱為簡單回路。

9）連通、連通圖和連通分量

通過路徑的概念，可以進一步研究圖結構的連通關系，主要涉及如下內容：

?如果圖結構中兩個頂點之間有路徑，則稱這兩個頂點是連通的。這里需要注意連通的兩個頂點可以不是鄰接頂點，只要有路徑連接即可，可以途經多個頂點。

?如果無向圖中任意兩個頂點都是連通的，那么這個圖便稱為連通圖。如果無向圖中包含兩個頂點是不連通的，那么這個圖便稱為非連通圖。

?無向圖的極大連通子圖稱為該圖的連通分量。

理論可以證明，對于一個連通圖，其連通分量有且只有一個，那就是該連通圖自身。而對于一個非連通圖，則有可能存在多個連通分量。例如，圖2-33中，圖（a）為一個非連通圖，因為其中頂點V2和頂點V3之間沒有路徑。這個非連通圖中的連通分量包括兩個，分別為圖（b）和圖（c）。

10）強連通圖和強連通分量

與無向圖類似，在有向圖中也有連通的概念，主要涉及如下內容：

?如果兩個頂點之間有路徑，也稱這兩個頂點是連通的。需要注意的是，有向圖中邊是有方向的。因此，有時從Vi到Vj是連通的，但從Vj到Vi卻不一定連通。

?如果有向圖中任意兩個頂點都是連通的，則稱該圖為強連通圖。如果有向圖中包含兩個頂點不是連通的，則稱該圖為非強連通圖。

?有向圖的極大強連通子圖稱為該圖的強連通分量。

理論上可以證明，強連通圖只有一個強連通分量，那就是該圖自身。而對于一個非強連通圖，則有可能存在多個強連通分量。例如，在圖2-34中，圖（a）為一個非強連通圖，因為其中頂點V2和頂點V3之間沒有路徑。這個非強連通圖中的強連通分量有兩個，如圖（b）和圖（c）所示。

11）權

在前面介紹圖的時候，各個邊并沒有賦予任何含義。在實際的應用中往往需要將邊表示成某種數值，這個數值便是該邊的權（Weight）。無向圖中加入權值，則稱為無向帶權圖。有向圖中加入權值，則稱為有向帶權圖。典型的無向帶權圖和有向帶權圖，如圖2-35所示。

權在實際應用中可以代表各種含義，例如，在交通圖中表示道路的長度，在通信網絡中表示基站之間的距離，在人際關系中代表親密程度等。

12）網（Network）

網即邊上帶有權值的圖的另一名稱。網的概念與實際應用更為貼切。

2.8.3　準備數據

學習了前面的理論知識后，下面就開始圖結構的程序設計。首先需要準備數據，即準備在圖結構操作中需要用到的變量及數據結構等。由于圖是一種復雜的數據結構，頂點之間存在多對多的關系，因此無法簡單地將頂點映射到內存中。

在實際應用中，通常需要采用結構數組的形式來單獨保存頂點信息，然后采用二維數組的形式保存頂點之間的關系。這種保存頂點之間關系的數組稱為鄰接矩陣（Adjacency Matrix）。

這樣，對于一個包含n個頂點的圖，可以使用如下語句來聲明一個數組保存頂點信息，聲明一個鄰接矩陣保存邊的權。

char[] Vertex=new char[MaxNum]；//保存頂點信息（序號或字母））

int[][] EdgeWeight=new int[MaxNum][MaxNum]；//保存邊的權

對于數組Vertex，其中每一個數組元素保存頂點信息，可以是序號或者字母。而鄰接矩陣EdgeVeight保存邊的權或者連接關系。

在表示連接關系時，該二維數組中的元素EdgeVeight[i][j]=1表示（Vi，Vj）或<Vi，Vj>構成一條邊，如果EdgeVeight[i][j]=0表示（Vi，Vj）或<Vi，Vj>不構成一條邊。例如，對于圖2-36所示的無向圖，可以采用一維數組來保存頂點，保存的形式如圖2-37所示。

示例代碼如下：

對于鄰接矩陣，可以按照如圖2-38所示進行存儲。對于有邊的兩個頂點，在對應的矩陣元素中填入1。例如，V1和V3之間存在一條邊，因此EdgeVeight[1][3]中保存1，而V3和V1之間存在一條邊，因此EdgeVeight[3][1]中保存1。因此可見，對于無向圖，其鄰接矩陣左下角和右上角是對稱的。

對于有向圖，如圖2-39所示。保存頂點的一維數組形式不變，如圖2-40所示。而對于鄰接矩陣，仍然采用二維數組，其保存形式如圖2-41所示。對于有邊的兩個頂點，在對應的矩陣元素中保存1。這里需要注意，邊是有方向的。

例如，頂點V2到頂點V3存在一條邊，因此在EdgeVeight[2][3]中保存1，而頂點V3到頂點V2不存在邊，因此在EdgeVeight[3][2]中保存0。

對于帶有權值的圖來說，鄰接矩陣中可以保存相應的權值。也就是說，此時，有邊的項保存對應的權值，而無邊的項則保存一個特殊的符號Z。例如，對于圖2-42所示的有向帶權圖，其對應的鄰接矩陣，如圖2-43所示。

這里需要注意的是，在實際程序中為了保存帶權值的圖，往往定義一個最大值MAX，其大于所有邊的權值之和，用MAX來替代特殊的符號Z保存在二維數組中。

學習了前面的理論知識后，可以在程序中準備相應的數據用于保存圖結構。示例代碼如下：

在上述代碼中，定義了圖的最大頂點數MaxNum和用于保存特殊符號Z的最大值MaxValue。鄰接矩陣圖結構為GraphMatrix，其中包括保存頂點信息的數組Vertex，圖的類型GType、頂點的數量VertexNum、邊的數量EdgeNum、保存邊的權的二維數組EdgeWeight及遍歷標志數組isTrav。

2.8.4　創建圖

在使用圖結構之前，首先要創建并初始化一個圖。代碼示例如下：

在上述代碼中，輸入參數GM為一個指向圖結構的引用。程序中，由用戶輸入頂點信息和邊的信息。對于邊來說，需要輸入起始頂點、結束頂點和權值，各項以空格分割。最后，判斷是否為無向圖，因為無向圖還需將邊的權值保存到對角位置。

2.8.5　清空圖

清空圖即將一個圖結構變成一個空圖，這里只需將矩陣中各個元素設置為MaxValue即可。清空圖的示例代碼如下：

在上述代碼中，輸入參數GM為一個指向圖結構的引用。程序中，通過雙重循環為矩陣中各個元素賦值MaxValue，表示這是一個空圖。

2.8.6　顯示圖

顯示圖即顯示圖的鄰接矩陣，用戶可以通過鄰接矩陣方便地了解圖的頂點和邊等結構信息。顯示圖的示例代碼如下：

在上述代碼中，輸入參數GM為一個指向圖結構的引用。在程序中，首先在第1行輸出頂點信息。然后，逐個輸出矩陣中的每個元素。這里，以Z表示無窮大MaxValue。

2.8.7　遍歷圖

遍歷圖即逐個訪問圖中所有的頂點。由于圖的結構復雜，存在多對多的特點，因此，當順著某一路徑訪問過某頂點后，可能還會順著另一路徑回到該頂點。同一頂點被多次訪問浪費了大量時間，使得遍歷的效率低。

為了避免這種情況，可在圖結構中設置一個數組isTrav[n]，該數組各元素的初始值為0，當某個頂點被遍歷訪問過，則設置對應的數據元素值為1。在訪問某個頂點i時，先判斷數組isTrav[i]中的值，如果其值為1，則繼續路徑的下一個頂點；如果其值為0，則訪問當前頂點（進行相應的處理），然后繼續路徑的下一個頂點。

常用的遍歷圖的方法有兩種：廣度優先遍歷法和深度優先遍歷法。下面以深度優先遍歷法為例進行介紹。深度優先遍歷法類似于樹的先序遍歷，具體執行過程如下：

（1）從數組isTrav中選擇一個未被訪問的頂點Vi，將其標記為1，表示已訪問。

（2）從Vi的一個未被訪問過的鄰接點出發進行深度優先遍歷。

（3）重復步驟（2），直至圖中所有和Vi有路徑相通的頂點都被訪問過。

（4）重復步驟（1）至步驟（3）的操作，直到圖中所有頂點都被訪問過。

深度優先遍歷法是一個遞歸過程，具體的程序代碼示例如下：

在上述代碼中，方法DeepTraOne（）從第n個結點開始深度遍歷圖，其輸入參數GM為一個指向圖結構的引用，輸入參數n為頂點編號。程序中通過遞歸進行遍歷。

方法DeepTraGraph（）用于執行完整的深度優先遍歷，以訪問所有的頂點。其中，輸入參數GM為一個指向圖結構的引用。程序中通過調用方法DeepTraOne（）來完成所有頂點的遍歷。

2.8.8　圖結構操作實例

學習了前面的圖結構的基本運算之后，便可以輕松地完成對圖結構的各種操作。下面給出一個完整的例子，來演示圖結構的創建和遍歷等操作。完整的程序代碼示例如下：

【程序2-6】

在主方法中，首先由用戶輸入圖的種類，0表示無向圖，1表示有向圖。然后，由用戶輸入頂點數和邊數。接著清空圖，并按照用戶輸入的數據生成鄰接表結構的圖。最后，輸出鄰接矩陣并執行深度優先遍歷法來遍歷整個圖。

整個程序的執行結果，如圖2-44所示。這里輸入的是一個無向圖，包含4個頂點和6條邊。