【文章內容簡介】 ，或者說， A中的元素 aij表示了結點 vi和結點 vj（ 0≤j≤n1）的鄰接關系，所以矩陣 A稱作 鄰接矩陣 。 無向圖及其鄰接矩陣 有向圖及其鄰接矩陣帶權圖及其鄰接矩陣 圖的鄰接表存儲結構 圖的鄰接矩陣存儲結構的主要特點是把圖的邊信息存儲在一個 nn矩陣中，其中 n為圖中的結點個數。 有向圖的鄰接表存儲結構 鄰接矩陣圖類 ? 鄰接矩陣圖類 AdjMWGraph 的設計? 鄰接矩陣圖類 AdjMWGraph 的測試 圖的遍歷 圖的深度和廣度優(yōu)先遍歷算法 圖的遍歷算法設計需要考慮三個問題： （ 1）圖的特點是沒有首尾之分，所以算法的參數要指定訪問的第一個結點； （ 2）對圖的遍歷路徑有可能構成一個回路，從而造成死循環(huán)，所以算法設計要考慮遍歷路徑可能出現的死循環(huán)問題； （ 3）一個結點可能和若干個結點都是鄰接結點，要使一個結點的所有鄰接結點按照某種次序被訪問。1 圖的深度優(yōu)先遍歷算法 連通圖的深度優(yōu)先遍歷遞歸算法為：（ 1）訪問結點 v并標記結點 v為已訪問；（ 2）查找結點 v的第一個鄰接結點 w；（ 3）若結點 v的鄰接結點 w存在，則繼續(xù)執(zhí)行，否則算法結束；（ 4）若結點 w尚未被訪問則深度優(yōu)先搜索遞歸訪問結點w；（ 5）查找結點 v的 w鄰接結點的下一個鄰接結點 w，轉到步驟（ 3）。 2 圖的廣度優(yōu)先遍歷算法 連通圖的廣度優(yōu)先遍歷算法為： （ 1）訪問初始結點 v并標記結點 v為已訪問；（ 2）結點 v入隊列；（ 3）當隊列非空時則繼續(xù)執(zhí)行，否則算法結束；（ 4）出隊列取得隊頭結點 u；（ 5）查找結點 u的第一個鄰接結點 w；（ 6）若結點 u的鄰接結點 w不存在，則轉到步驟（ 3），否則循環(huán)執(zhí)行， （ ）若結點 w尚未被訪問，則訪問結點 w，并標記結點 w為已訪問； （ ）結點 w入隊列； （ ）查找結點 u的 w鄰接結點后的下一個鄰接結點 w，轉到步驟（ 6）。3 非連通圖的遍歷 對于連通圖，從圖的任意一個結點開始深度或廣度優(yōu)先遍歷，一定可以訪問圖中的所有結點。但對于非連通圖，從圖的任意一個結點開始深度或廣度優(yōu)先遍歷，并不能訪問圖中的所有結點。對于非連通圖，從圖的任意一個結點開始深度或廣度優(yōu)先遍歷只能訪問和初始結點連通的所有結點。 圖的深度和廣度優(yōu)先遍歷成員函數設計1 訪問結點2 深度和廣度優(yōu)先遍歷成員函數設計3 測試程序 最小生成樹 最小生成樹的基本概念 一個有 n個結點的連通圖的 生成樹 是原圖的極小連通子圖，它包含原圖中的所有 n個結點，并且有保持圖連通的最少的邊。 如果無向連通圖是一個帶權圖，那么它的所有生成樹中必有一棵邊的權值總和最小的生成樹，我們稱這棵生成樹為 最小代價生成樹 ，簡稱 最小生成樹 。無向圖和它的不同的生成樹 從最小生成樹的定義可知，構造有 n個結點的無向連通帶權圖的最小生成樹 ,必須滿足以下三條： （ 1）構造的最小生成樹必須包括 n個結點； （ 2）構造的最小生成樹中有且只有 n1條邊； （ 3）構造的最小生成樹中不存在回路。 構造最小生成樹的方法有許多種，典型的構造方法有兩種，一種稱作 普里姆 （ Prim）算法，另一種稱作 克魯斯卡爾 （ Kruskal）算法。1 普里姆算法思想 假設 G=(V,E)為一個帶權圖，其中 V為帶權圖中結點的集合， E為帶權圖中邊的權值集合。設置兩個新的集合 U和 T，其中 U用于存放帶權圖 G的最小生成樹的結點的集合， T用于存放帶權圖 G的最小生成樹的權值的集合。 普里姆算法思想 是：令集合 U的初值為 U={u0}（即假設構造最小生成樹時從結點 u0開始），集合 T的初值為 T={}。從所有結點 u∈ U和結點 v∈ VU的帶權邊中選出具有最小權值的邊 (u,v)，將結點 v加入集合 U中，將邊 (u,v) 加入集合 T中。如此不斷重復，當 U=V時則最小生成樹構造完畢。此時集合 U中存放著最小生成樹結點的集合，集合 T中存放著最小生成樹邊的權值集合。普里姆算法構造最小生成樹的過程2 普里姆函數設計 這里我們令當弧頭結點等于弧尾結點時權值等于 0。 函數的參數設計： 普里姆函數應有兩個參數： 一個參數是圖 g，這里圖 g定義為鄰接矩陣存儲結構圖類的對象； 另一個參數是通過函數得到的最小生成樹的結點數據和相應結點的邊的權值數據 closeVertex。普里姆算法運行時數組 lowCost的變化過程 克魯斯卡爾算法 克魯斯卡爾 算法是：設無向連通帶權圖 G=(V,E)，其中 V為結點的集合， E為邊的集合。設帶權圖 G的最小生成樹 T由結點集合和邊的集合構成，其初值為 T=(V,{})，即初始時最小生成樹 T只由帶權圖 G中的結點集合組成，各結點之間沒有一條邊。這樣，最小生成樹 T中的各個結點各自構成一個連通分量。然后，按照邊的權值遞增的順序考察帶權圖 G中的邊集合 E中的各條邊。若被考察的邊的兩個結點屬于 T的兩個不同的連通分量，則將此邊加入到最小生成樹 T，同時把兩個連通分量連接為一個連通分量；若被考察的邊的兩個結點屬于 T的同一個連通分量，則將此邊舍去。如此下去，當 T中的連通分量個數為 1時， T中的該連通分量即為帶權圖 G的一棵最小生成樹?？唆斔箍査惴嬙熳钚∩蓸涞倪^程 最短路徑 最短路徑的基本概念 在一個圖中，若從一個結點到另一個結點存在著路徑，定義 路徑長度 為一條路徑上所經過的邊的數目。圖中從一個結點到另一個結點可能存在著多條路徑，我們把路徑長度最短的那條路徑叫做 最短路徑 ，其路徑長度叫做 最短路徑 長度或 最短距離 . 在一個帶權圖中，若從一個結點到另一個結點存在著一條路徑，則稱該路徑上所經過邊的權值之和為該路徑上的 帶權路徑長度 。帶權圖中從一個結點到另一個結點可能存在著多條路徑，我們把帶權路徑長度值最小的那條路徑也叫做 最短路徑 ，其帶權路徑長度也叫做 最短路徑長度 或 最短距離 。 從一個點到其余各結點的最點路徑 1 狄克斯特拉算法思想 狄克斯特拉算法 是：設置兩個結點的集合 S和 T，集合 S中存放已找到最短路徑的結點，集合 T中存放當前還未找到最短路徑的結點。初始狀態(tài)時，集合 S中只包含源點，設為 v0，然后從集合 T中選擇到源點 v0路徑長度最短的結點 u加入到集合 S中，集合 S中每加入一個新的結點 u都要修改源點 v0到集合 T中剩余結點的當前最短路徑長度值，集合 T中各結點的新的當前最短路徑長度值，為原來的當前最短路徑長度值與從源點過結點 u到達該結點的路徑長度中的較小者。此過程不斷重復，直到集合 T中的結點全部加入到集合 S 中為止。 下圖為意示例： 每對結點之間的最短路徑 弗洛伊德算法是：設矩陣 cost用來存放帶權有向圖 G的權值，即矩陣元素 cost[i][j]中存放著下標為 i的結點到下標為 j的結點之間的權值，可以通過遞推構造一個矩陣序列 A0,A1,A2,……,AN 來求每對結點之間的最短路徑。初始時有， A0[i][j]=cost[i][j]。當已經求出Ak,要遞推求解 Ak+1時，可分兩種情況來考慮：一種情況是該路徑不經過下標為 k+1的結點，此時該路徑長度與從結點 vi到結點 vj的路徑上所經過的結點下標不大于 k的最短路徑長度相同；另一種情況是該路徑經過下標為 k+1的結點，此時該路徑可分為兩段，一段是從結點 vi到結點 vk+1的最短路徑，另一段是從結點 vk+1到結點 vj的最短路徑，此時的最短路徑長度等于這兩段最短路徑長度之和。這兩種情況中的路徑長度較小者，就是要求的從結點 vi到結點 vj的路徑上所經過的結點下標不大于 k+1的最短路徑長度。弗洛伊德算法的算法思想可用如下遞推公式描述： A0[i][j]=cost[i][j] Ak+1[i][j]=min{Ak[i][j], Ak[i][k+1]+Ak[k+1][j]} （0≤k≤n1） 也就是說，初始時， A0[i][j]=cost[i][j]，然后進行遞推，每遞推一次，從結點 vi到結點 vj的最短路徑上就多考慮了一個經過的中間結點，這樣，經過 n次遞推后得到的 An[i][j]就是考慮了經過圖中所有結點情況下的從結點 vi到結點 vj的最短路徑長度。第 9章 排序 排序的基本概念 插入排序 交換排序 歸并排序 基數排序 各種排序算法的性能比較本章主要知識點：● 排序的基本概念和衡量排序算法優(yōu)劣的標準，其中衡量標準有算法的時間復雜度、空間復雜度和穩(wěn)定性● 直接插入排序，希爾排序● 直接選擇排序，堆排序● 冒泡排序，快速排序● 歸并排序● 基數排序● 各種排序算法的性能比較 排序的基本概念 排序 是對數據元素序列建立某種有序排列的過程。 關鍵 字是要排序的數據元素集合中的一個域，排序是以關鍵字為基準進行的。 關鍵字 分 主關鍵字 和 次關鍵字 兩種。對要排序的數據元素集合來說，如果關鍵字滿足數據元素值不同時該關鍵字的值也一定不同，這樣的關鍵字稱為 主關鍵字 。 不滿足主關鍵字定義的關鍵字稱為 次關鍵字。 學生成績表 排序 分 內部排序 和 外部排序 兩種。 內部排序是把待排數據元素全部調入內存中進行的排序。如果數據元素的數量太大，需要分批導入內存，分批導入內存的數據元素排好序后再分批導出到磁盤和磁帶外存介質上的排序方法稱作 外部排序。 排序算法的比較標準： 1. 空間復雜度 2. 時間復雜度 3. 穩(wěn)定性 插入排序 直插入排序 直接插入排序 的基本思想是：順序地把待排序的數據元素按其值的大小插入到已排序數據元素子集合的適當位置。子集合的數據元素個數從只有一個數據元素開始逐次增大。當子集合大小最終和集合大小相同時排序完畢。 直接插入排序過程 希爾排序 希爾排序 的基本思想是：把待排序的數據元