|
這節(jié)，我們主要討論，一下克魯斯卡爾算法實(shí)現(xiàn) 最小生成樹。 克魯斯卡爾算法的基本思想是：對一個(gè)有 n個(gè)頂點(diǎn)的無向連通網(wǎng)，將圖中的邊按權(quán)值大小依次選取，若選取的邊使生成樹不形成回路，則把它加入到樹中；若形成回路，則將它舍 棄。如此進(jìn)行下去，直到樹中包含有 n-1條邊為止。 以下圖 (a)為例說明用克魯斯卡爾算法求無向連通網(wǎng)最小生成樹的過程。
實(shí)現(xiàn)源代碼如下：  public int[] Klausi() { int[] lowcost = new int[nodes.Length]; //權(quán)值數(shù)組 保存權(quán)值的數(shù)組 int[] closevex = new int[nodes.Length]; //頂點(diǎn)數(shù)組 保存 相應(yīng)各個(gè)頂點(diǎn)的數(shù)組 int mincost = int.MaxValue; //最小權(quán)值 默認(rèn)是 int的最大值 表示無窮大 //輔助數(shù)組初始化 對摸個(gè) 權(quán)值數(shù)組賦值 保存 最小值 for (int i = 1; i < nodes.Length; ++i) { lowcost[i] = matrix[0, i]; closevex[i] = 0; } //某個(gè)頂點(diǎn)加入集合U lowcost[0] = 0; closevex[0] = 0; //判斷最小的權(quán)值通過的頂點(diǎn)的循環(huán)就此開始 for(int i=0; i<nodes.Length; ++i) { int k = 1; int j = 1; //選取權(quán)值最小的邊和相應(yīng)的頂點(diǎn) while(j < nodes.Length) { if (lowcost[j] < mincost && lowcost[j] != 0) { k = j; } ++j; } //新頂點(diǎn)加入集合U lowcost[k] = 0; //重新計(jì)算該頂點(diǎn)到其余頂點(diǎn)的邊的權(quán)值 for (j = 1; j < nodes.Length; ++j) { if (matrix[k, j] < lowcost[j]) { lowcost[j] = matrix[k, j]; closevex[j] = k; } } } return closevex; } //我們明顯的看出來，由于用到了雙重循環(huán)，其算法的時(shí)間的復(fù)雜度是O(n^2) 介紹了最短路徑的概念 最短路徑問題是圖的又一個(gè)比較典型的應(yīng)用問題。例如，n個(gè)城市之間的一個(gè)公路網(wǎng)，給定這些城市之間的公路的距離，能否找到城市 A 到城市 B 之間一條距離最近的通路呢？如果城市用頂點(diǎn)表示，城市間的公路用邊表示，公路的長度作為邊的權(quán)值。那么，這個(gè)問題就可歸結(jié)為在網(wǎng)中求頂點(diǎn) A 到頂點(diǎn) B 的所有路徑中邊的權(quán)值之和最小的那一條路徑， 這條路徑就是兩個(gè)頂點(diǎn)之間的最短路徑(Shortest Path)，并稱路徑上的第一個(gè)頂點(diǎn)為源點(diǎn)（Source） ，最后一個(gè)頂點(diǎn)為終點(diǎn)（Destination） 。在不帶權(quán)的圖中，最短路徑是指兩個(gè)頂點(diǎn)之間經(jīng)歷的邊數(shù)最少的路徑。 最短路徑可以是求某個(gè)源點(diǎn)出發(fā)到其它頂點(diǎn)的最短路徑， 也可以是求網(wǎng)中任意兩個(gè)頂點(diǎn)之間的最短路徑。這里只討論單源點(diǎn)的最短路徑問題，感興趣的讀者可參考有關(guān)文獻(xiàn)，了解每一對頂點(diǎn)之間的最短路徑。 網(wǎng)分為無向網(wǎng)和有向網(wǎng)，當(dāng)把無向網(wǎng)中的每一條邊(vi,vj)都定義為弧<vi,vj>和弧<vj,vi>，則有向網(wǎng)就變成了無向網(wǎng)。因此，不失一般性，我們這里只討論有向網(wǎng)上的最短路徑問題。 下圖是一個(gè)有向網(wǎng)及其鄰接矩陣。該網(wǎng)從頂點(diǎn) A 到頂點(diǎn) D 有 4條路徑，分別是：路徑（A,D） ，其帶權(quán)路徑長度為 30；路徑（A,C,F,D） ，其帶權(quán)路徑長度為 22；路徑（A,C,B,E,D） ，其帶權(quán)路徑長度為 32；路徑（A,C,F,E,D） ，其帶權(quán)路徑長度為 34。路徑（A,C,F,D）稱為最短路徑，其帶權(quán)路徑長度 22稱為最短距離。
他用的是狄克斯特拉（Dikastra）算法 對于求單源點(diǎn)的最短路徑問題，狄克斯特拉（Dikastra）提出了一個(gè)按路徑長度遞增的順序逐步產(chǎn)生最短路徑的構(gòu)造算法。狄克斯特拉的算法思想是：設(shè)置兩個(gè)頂點(diǎn)的集合 S 和T， 集合 S 中存放已找到最短路徑的頂點(diǎn)， 集合 T 中存放當(dāng)前還未找到最短路徑的頂點(diǎn)。初始狀態(tài)時(shí)，集合 S 中只包含源點(diǎn)，設(shè)為 v0，然后從集合 T 中選擇到源點(diǎn) v0路徑長度最短的頂點(diǎn) u加入到集合 S 中，集合 S 中每加入一個(gè)新的頂點(diǎn) u都要修改源點(diǎn) v0到集合 T 中剩余頂點(diǎn)的當(dāng)前最短路徑長度值，集合 T 中各頂點(diǎn)的新的最短路徑長度值為原來的當(dāng)前最短路徑長度值與從源點(diǎn)過頂點(diǎn) u到達(dá)該頂點(diǎn)的新的最短路徑長度中的較小者。此過程不斷重復(fù)，直到集合 T 中的頂點(diǎn)全部加到集合 S 中為止。 以下圖為例說明用狄克斯特拉算法求有向網(wǎng)的從某個(gè)頂點(diǎn)到其余頂點(diǎn)最短路徑的過程。 第一步：列出頂點(diǎn) A 到其余各頂點(diǎn)的路徑長度，它們分別為 0、∞、5、30、∞、∞。從中選取路徑長度最小的頂點(diǎn) C（從源點(diǎn)到頂點(diǎn) C 的最短路徑為 5） 。
、有向網(wǎng)的鄰接矩陣類的實(shí)現(xiàn) public class DirecNetAdjMatrix<T> : IGraph<T>//繼承圖形的接口 { private Node<T>[] nodes; //頂點(diǎn)數(shù)組 存取相應(yīng)的結(jié)點(diǎn)的 泛型數(shù)組 private int numEdges; //邊的數(shù)目 上圖邊數(shù)字是6 private int[,] matrix; //鄰接矩陣數(shù)組 存取相應(yīng)的互相的權(quán)值 //構(gòu)造器 進(jìn)行數(shù)據(jù)的初始化 邊的數(shù)目是0 public NetAdjMatrix (int n) { nodes = new Node<T>[n]; matrix = new int[n,n]; numEdges = 0; } //獲取索引為index的頂點(diǎn)的信息 算法的時(shí)間復(fù)雜度是O(1) public Node<T> GetNode(int index) { return nodes[index]; } //設(shè)置索引為index的頂點(diǎn)的信息 算法的時(shí)間復(fù)雜度是O(1) public void SetNode(int index, Node<T> v) { nodes[index] = v; } //邊的數(shù)目屬性 可讀可寫的屬性 public int NumEdges { get { return numEdges; } set { numEdges = value; } } //獲取matrix[index1, index2]的值 算法的時(shí)間復(fù)雜度是O（1） public int GetMatrix(int index1, int index2) { return matrix[index1, index2]; } //設(shè)置matrix[index1, index2]的值 算法的復(fù)雜度是O(1) public void SetMatrix(int index1, int index2, int v) { matrix[index1, index2] = v; } //獲取頂點(diǎn)的數(shù)目 算法的時(shí)間的復(fù)雜度是O(1) public int GetNumOfVertex() { return nodes.Length; } //獲取邊的數(shù)目 算法的時(shí)間的復(fù)雜度是O(1) public int GetNumOfEdge() { return numEdges; } //v是否是無向網(wǎng)的頂點(diǎn) //如果包含這個(gè)頂點(diǎn) 返回為真，否則返回為假。 //由于這是一層循環(huán)，算法的復(fù)雜度是O(n) public bool IsNode(Node<T> v) { //遍歷頂點(diǎn)數(shù)組 foreach (Node<T> nd in nodes) { //如果頂點(diǎn)nd與v相等，則v是圖的頂點(diǎn)，返回true if (v.Equals(nd)) { return true; } } return false; } //獲得頂點(diǎn)v在頂點(diǎn)數(shù)組中的索引 // 如果相等，返回相應(yīng)的索引。 //由于是一層循環(huán)，時(shí)間的復(fù)雜度是O(n) public int GetIndex(Node<T> v) { int i = -1; //遍歷頂點(diǎn)數(shù)組 for (i = 0; i < nodes.Length; ++i) { //如果頂點(diǎn)nd與v相等，則v是圖的頂點(diǎn)，返回索引值 if (nodes[i].Equals(v)) { return i; } } return i; } //在頂點(diǎn)v1、v2之間添加權(quán)值為v的邊 //添加相應(yīng)的權(quán)值的v的邊， 這是一個(gè)對稱矩陣。 public void SetEdge(Node<T> v1, Node<T> v2, int v) { //v1或v2不是無向網(wǎng)的頂點(diǎn) if (!IsNode(v1) || !IsNode(v2)) { Console.WriteLine("Node is not belong to Graph!"); return; } //矩陣是對稱矩陣 matrix[GetIndex(v1), GetIndex(v2)] = v; matrix[GetIndex(v2), GetIndex(v1)] = v; ++numEdges; } //刪除v1和v2之間的邊 // 刪除對稱矩陣。 public void DelEdge(Node<T> v1, Node<T> v2) { //v1或v2不是無向網(wǎng)的頂點(diǎn) if (!IsNode(v1) || !IsNode(v2)) { Console.WriteLine("Node is not belong to Graph!"); return; } //v1和v2之間存在邊 if (matrix[GetIndex(v1), GetIndex(v2)] != int.MaxValue) { //矩陣是對稱矩陣 matrix[GetIndex(v1), GetIndex(v2)] = int.MaxValue; matrix[GetIndex(v2), GetIndex(v1)] = int.MaxValue; --numEdges; } } //判斷v1和v2之間是否存在邊 //判斷相應(yīng) 不是 最大值 返回為真 否則 為假 算法的時(shí)間復(fù)雜度O(1) public bool IsEdge(Node<T> v1, Node<T> v2) { //v1或v2不是無向網(wǎng)的頂點(diǎn) if (!IsNode(v1) || !IsNode(v2)) { Console.WriteLine("Node is not belong to Graph!"); return false; } //v1和v2之間存在邊 if (matrix[GetIndex(v1), GetIndex(v2)] != int.MaxValue) { return true; } Else //v1和v2之間不存在邊 { return false; } } } 為實(shí)現(xiàn)狄克斯特拉算法，引入兩個(gè)數(shù)組，一個(gè)一維數(shù)組 ShortPathArr，用來保存從源點(diǎn)到各個(gè)頂點(diǎn)的最短路徑的長度，一個(gè)二維數(shù)組 PathMatrixArr，用來保存從源點(diǎn)到某個(gè)頂點(diǎn)的最短路徑上的頂點(diǎn)，如 PathMatrix[v][w]為 true，則 w從源點(diǎn)到頂點(diǎn) v 的最短路徑上的頂點(diǎn)。為了該算法的結(jié)果被其他算法使用，把這兩個(gè)數(shù)組作為算法的參數(shù)使用。另外，為了表示某頂點(diǎn)的最短路徑是否已經(jīng)找到，在算法中設(shè)了一個(gè)一維數(shù)組 final,如果 final[i]為 true,則表示已經(jīng)找到第 i 個(gè)頂點(diǎn)的最短路徑。i 是該頂點(diǎn)在鄰接矩陣中的序號。同樣，把該算法作為類DirecNetAdjMatrix<T>的成員方法來實(shí)現(xiàn)。 //pathMatricArr用來保存從源點(diǎn)到某個(gè)頂點(diǎn)的最短路徑上的頂點(diǎn) //ShortPathArr用來保存從源點(diǎn)到各個(gè)頂點(diǎn)的最短路徑的長度 如圖所示：
當(dāng)然，圖的應(yīng)用還有很多了，點(diǎn)到為止。 至于圖的總結(jié)是：
所謂的圖是圖狀結(jié)構(gòu)簡稱圖，是另一種非線性結(jié)構(gòu)，它比樹形結(jié)構(gòu)更復(fù)雜。樹形結(jié)構(gòu)中的結(jié)點(diǎn)是一對多的關(guān)系，結(jié)點(diǎn)間具有明顯的層次和分支關(guān)系。每一層的結(jié)點(diǎn)可以和下一層的多個(gè)結(jié)點(diǎn)相關(guān)，但只能和上一層的一個(gè)結(jié)點(diǎn)相關(guān)。而圖中的頂點(diǎn)（把圖中的數(shù)據(jù)元素稱為頂點(diǎn)）是多對多的關(guān)系，即頂點(diǎn)間的關(guān)系是任意的，圖中任意兩個(gè)頂點(diǎn)之間都可能相關(guān)。也就是說，圖的頂點(diǎn)之間無明顯的層次關(guān)系，這種關(guān)系在現(xiàn)實(shí)世界中大量存在。因此，圖的應(yīng)用相當(dāng)廣泛，在自然科學(xué)、社會科學(xué)和人文科學(xué)等許多領(lǐng)域都有著非常廣泛的應(yīng)用。例如搜索引擎，地圖等等。 |
|
|
