1.5.3　樹與圖

1．樹

樹狀結構是以分支關系定義的層次結構，它是一種重要的非線性結構。該結構在客觀世界中廣泛存在，例如人類的家庭族譜、各種社會組織機構、計算機文件管理和信息組織方面都用到該結構。

（1）樹的定義。

定義5　樹是由n（n≥0）個結點組成的有限集。在任意一棵非空樹中，有且僅有一個特定的結點稱為該樹的根結點，當n>1時，根結點之外的其余結點可分為m（m≥0）個互不相交的有限集合T₁，T₂，…，T_m，其中每個集合本身又是一棵樹，稱為根的子樹。樹的示意圖如圖1-7所示。

圖1-7是一棵由11個結點組成的樹T。其中A是根結點，其余結點分為3個互不相交的有限子集：T₁={B，E，F，K}，T₂={C，G}，T₃={D，H，I，J}，T₁，T₂，T₃都是根A的子樹，這3棵子樹的根結點分別是B，C，D，每棵子樹本身也是一棵樹，可繼續劃分。例如子樹T₃以D為根結點，子樹的其余結點又可分為3個互不相交的子集T₃₁={H}，T₃₂={I}，T₃₃={J}，而T₃₁、T₃₂和T₃₃又是只有一個根結點的樹。

（2）樹結構中的重要術語。

父結點：若一個結點有子樹，則該結點為父結點（或稱為雙親結點）。

孩子結點：若某結點有子樹，則其子樹的根為該結點的孩子結點。

兄弟結點：同一個結點的孩子結點。

層次：結點的層次是從根結點開始定義的，根結點的層次為1，其余結點的層次是其父結點的層次加1。若某結點在第i層，則其子樹的根就在第i+1層。

結點的深度：結點所在的層次減1。

樹的高度（深度）：樹中結點的最大深度。

度：結點擁有的子樹數目稱為該結點的度，即一個結點的孩子數目就是該結點的度。

葉子結點：度為0的結點。

森林：森林是m（m≥0）棵互不相交的樹的集合，對樹中每個結點而言，其子樹的集合即為森林。

二叉樹：二叉樹是一種非常重要的樹狀結構，它的特點是每個結點至多只有兩棵子樹，并且，二叉樹的子樹有左右之分，其次序有時不能任意顛倒。

例如，對于如圖1-7所示的樹，根結點A是結點B、C和D的父結點，結點B是結點E、F的父結點；結點B、C和D是結點A的孩子結點，并且B、C和D互為兄弟結點；結點A的層次是1、深度為0，結點B的層次為2、深度為1，結點K的層次為4、深度為3，因此該樹的深度為3；另外，結點A擁有的孩子結點數目為3，因此A的度為3，同樣結點C的度為1，結點F的度為0，可見F為葉子結點，圖1-7中所示的F，G，H，I，J都是該樹的葉子結點。

（3）樹的存儲結構。

與線性結構類似，樹的存儲結構也可以采用順序存儲結構和鏈式存儲結構兩種方式。在大量的應用中，人們曾使用多種形式的存儲結構來表示樹，這里只介紹常用的幾種。

①順序存儲結構——雙親表示法。

由于樹中的每個結點可以有任意多棵子樹，結點的編號和孩子結點的編號不存在必然的關系，因此必須在結點中指出它們之間的父子關系。

雙親表示法是以一組連續的空間來存儲樹中的結點，并將樹中所有結點從上到下、從左至右依次編號，并用該編號作為結點在順序存儲中的位置。

樹中每個結點包含兩個域，即數據域（data）和雙親域（parent）。數據域存放結點的數據，雙親域存放雙親（父）結點在順序存儲中的位置編號。通過parent域，順序存儲的各個結點仍然保持正確的前驅-后繼關系。

【例1-8】　用雙親表示法順序存儲如圖1-8（a）所示的樹。

根據樹的順序存儲結構，采用雙親表示法順序存儲如圖1-8（a）所示的一棵樹，表示結果如圖1-8（b）所示。

由于根結點沒有父結點，因此將其parent域設置為-1。

這種結構利用了每個結點（除根外）只有唯一的父結點的性質，但是這種表示法在求結點的孩子時需要遍歷整個結構。

②鏈式存儲結構——孩子表示法。

把每個結點的孩子結點排列起來，看成一個線性表，且以單鏈表作為存儲結構，則n個結點有n個孩子鏈表（葉子結點的孩子鏈表為空表）。而n個頭指針又組成另外一個線性表。為了便于查找，可采用順序存儲結構。

與雙親表示法相反，孩子表示法便于那些涉及孩子的操作的實現，卻不適用于對雙親結點進行操作。為此，可以把二者結合起來。

③鏈式存儲結構——孩子兄弟表示法。

孩子兄弟表示法又稱二叉樹表示法或二叉鏈表表示法，即以二叉鏈表作為樹的存儲結構，鏈表中結點的兩個域分別指向該結點的第一個孩子結點和下一個兄弟結點。

利用這種存儲結構易于實現找結點孩子等操作。如果為每個結點增加一個parent域，則同樣能方便地實現對雙親的操作。

樹有十分重要的用途，如構造哈夫曼樹、最優二叉查找樹及解空間樹等，在實際的應用中，請讀者細細體會其奧妙吧。

2．圖

圖是一種比線性表和樹更為復雜的數據結構。在線性表中，數據元素之間僅存在線性關系，即每個元素只有一個直接前驅和一個直接后繼。在樹狀結構中，元素之間具有明顯的層次關系。每一個元素只能和上一層（如果存在的話）的一個元素相關，但可以和下一層的多個元素相關。在圖形結構中，元素之間的關系可以是任意的，一個圖中任意兩個元素都可以相關，即每個元素可以有多個前驅和多個后繼。

圖的應用最早可以追溯到18世紀，偉大的數學家歐拉（Euler）利用圖解決了著名的格尼斯堡七橋問題，這一創舉為圖在現代科學技術領域中的應用奠定了基礎。目前圖的應用極為廣泛，特別是近年來的迅速發展，已經滲入到諸如語言學、邏輯學、物理、電子電路分析及計算機學科中。

（1）圖的定義。

定義6　圖是一種數據結構，可以用二元組表示，圖中的數據元素通常稱為頂點（或結點），數據元素之間的關系稱為邊，其形式化定義為G=（V，E）。

其中，集合V是頂點集，即它是頂點的有窮非空集合；集合E是邊集，即它是V中兩個頂點之間的關系的有窮集。

在圖G中，若<v，w>∈E，則<v，w>表示從v到w的一條弧，v稱為弧尾或始點，w稱為弧頭或終點，此時的圖稱為有向圖。若<v，w>∈E必有<w，v>∈E，即E是對稱的，則以無序對（v，w）代替這兩個有序對，表示v和w之間的一條邊，此時的圖稱為無向圖。下面通過實例（如圖1-9所示）講述一下這兩種圖的區別及相應的形式化定義方法。

在圖1-9（a）中，每條邊的方向是用從始點指向終點的箭頭表示的，因此該圖是有向圖。該有向圖的形式化定義為G₁=（V₁，E₁）；頂點集V₁={v₁，v₂，v₃}；邊集E₁={<v₁，v₂>，<v₁，v₃>，<v₂，v₃>，<v₃，v₂>}；注意<v₃，v₂>與<v₂，v₃>表示兩條不同的邊。

圖1-9（b）中所示的每條邊都是沒有方向的，因此該圖為無向圖。該無向圖的形式化定義為G₂=（V₂，E₂）；頂點集V₂={v₁，v₂，v₃，v₄}；邊集E₂={（v₁，v₂），（v₁，v₃），（v₁，v₄），（v₂，v₃），（v₃，v₄）}；注意（v₂，v₁）與（v₁，v₂）表示同一條邊。

（2）圖的相關重要術語。

①鄰接點和相關邊。

對于無向圖G=（V，E），如果邊（v，w）∈E，則稱頂點v和w互為鄰接點，稱邊（v，w）依附于頂點v和w，即邊（v，w）是與頂點v和w相關聯的邊。

對于有向圖G=（V，E），如果<v，w>∈E，則稱頂點v鄰接到頂點w，頂點w鄰接于頂點v，而弧<v，w>是與頂點v和w相關聯的。

②路徑和回路。

路徑：在無向圖G=（V，E）中，從頂點v到頂點v′的路徑是一個頂點序列（v=v_i，0，v_i，1，…，v_i，_m=v′），其中（v_i，j-1，v_i，j）∈E，1≤j≤m。如果G是有向圖，則路徑也是有向的，頂點序列應滿足<v_i，j-1，v_i，_j>∈E，1≤j≤m。路徑的長度為路徑上的邊（或弧）的數目。

第一個頂點和最后一個頂點相同的路徑稱為回路或環。環的判斷也是一個非常重要的概念，在Kruskal算法中就涉及了對環的判斷。另外，有向無環圖是描述含有公共子式的表達式、一項工程及系統的進行過程的有效工具。

③權、網。

有時候圖中的邊或弧具有和其相關的數據，如表示一個頂點到另一個頂點的距離和費用，稱這些相關的數據為邊或弧的權，而這種帶權的圖稱為網。網示意圖如圖1-10所示。

④連通、生成樹。

在無向圖G中，如果從頂點v到頂點v′有路徑，則稱v和v′是連通的。如果圖中任意兩個頂點都是連通的，則稱G是連通圖。

在有向圖G中，如果對于每一對v，w∈V，v≠w，從v到w和從w到v都存在路徑，則稱G是強連通的。

一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點，但只能構成一棵樹的n-1條邊。同樣，生成樹是一個很重要的概念，例如在求解如何在最節省費用的前提下在n個城市間構造通信聯絡網時，就用到了最小生成樹的概念。在該概念的指導下，問題的解決將變得非常容易。

（3）圖的存儲結構。

圖的結構比較復雜，任意兩個頂點之間都可能存在聯系，因此無法以數據元素在存儲空間中的位置來表示元素之間的關系，即圖沒有順序映像的存儲結構，但可以借助數組來表示元素之間的關系。

常用圖的存儲結構有鄰接矩陣、鄰接表、鄰接多重表和十字鏈表。用多重鏈表表示圖是自然的事，它是一種最簡單的鏈式映像結構。另外，在實際的應用中，應根據具體的圖和所定義的運算，選擇恰當的存儲結構來使用。

①鄰接矩陣。

鄰接矩陣是表示圖中各頂點之間關系的矩陣，是圖的存儲結構之一。一般借助數組來實現。

定義7　假設G=（V，E）是一個有n個頂點的圖，規定各頂點的序號依次為1，2，3，…，n，則G的鄰接矩陣是一個具有如下定義的n階方陣：

對于帶權圖（或網），可以將上述定義改為

其中，W_i表示<v_i，v_j>弧或（v_i，v_j）邊上的權值。

例如，圖1-9（a）的鄰接矩陣為

圖1-9（b）的鄰接矩陣為

圖1-10（a）的鄰接矩陣為

圖1-10（b）的鄰接矩陣為

顯然，在無向圖中，鄰接矩陣是對稱的，因此僅需要存儲上三角或下三角的元素。

可見，一個圖可以用兩個數組來表示。其中一維數組用來存儲數據元素（即圖的頂點）的信息，二維數組用來存儲數據元素之間關系的信息（即圖中邊或弧的信息），即鄰接矩陣。借助鄰接矩陣很容易判定任意頂點之間是否存在邊（或?。?，并容易求得各頂點的度。

②鄰接表。

鄰接表是圖的一種鏈式存儲結構。在鄰接表中，圖中每個頂點對應一個單鏈表，第i個單鏈表中的結點表示依附于頂點v_i的邊（對于有向圖是以頂點v_i為尾的?。?。每個結點由三個域組成，鄰接點域指示與頂點v_i鄰接的點在圖中的位置，鏈域指示下一條邊或弧的結點，數據域存儲與邊或弧相關的信息。每個鏈表設置一個表頭結點，該結點中的鏈域指向鏈表中第一個結點，數據域用來存儲v_i的名稱或其他相關信息。

顯然，在邊稀疏的情況下，采用鄰接表表示圖比鄰接矩陣節省存儲空間，且在鄰接表中容易找到任一個頂點的第一個鄰接點和下一個鄰接點，但要判斷任意兩個頂點間是否存在邊就沒有鄰接矩陣方便了。

由于在鄰接表中，為了求某個頂點的入度則必須遍歷所有鏈表。因此，為了提高入度計算的效率，通常為圖建立一個逆鄰接表。逆鄰接表就是鏈表結點代表以v_i為弧頭的弧。

③十字鏈表。

十字鏈表是有向圖的另一種鏈式存儲結構。可以看成將有向圖的鄰接表和逆鄰接表結合起來得到的一種鏈表。在十字鏈表中，對應于有向圖中每一條弧有一個結點，對應于每個頂點也有一個結點。這兩個結點的結構示意圖如圖1-11所示。

在每條弧所對應的結點中，尾域tailvex和頭域headvex分別指示弧尾和弧頭這兩個頂點在圖中的位置，鏈域hlink指向弧頭相同的下一條弧頂點，而鏈域tlink指向弧尾相同的下一條弧頂點，info域指示該弧的相關信息。顯然，弧頭相同的弧在同一鏈表上，弧尾相同的弧也在同一鏈表上。它們的頭結點即為頂點結點，由三個域組成，其中data域存儲和頂點相關的信息，firstin和firstout鏈域分別指向以該頂點為弧頭或弧尾的第一個弧結點。

在十字鏈表中，既容易找到以v_i為尾的弧，也容易找到以v_i為頭的弧，因此在某些有向圖的應用中，十字鏈表是很有用的工具。

④鄰接多重表。

鄰接多重表是無向圖的另一種鏈式存儲結構。雖然鄰接表是無向圖的一種很有效的存儲結構，在鄰接表中很容易求得頂點和邊的各種信息。但是，在鄰接表中每一條邊（v_i，v_j）有兩個頂點，分別在第i個和第j個鏈表中，這給某些圖的操作帶來了不便。例如在某些圖中需要對已被搜索過的邊做標記等，此時需要找到表示同一條邊的兩個結點，在進行這一類操作時采用鄰接多重表作為存儲結構更為適宜。

鄰接多重表和十字鏈表類似。這里不再贅述。