演算法題的演示

Ⅰ 數學建模第四章 圖論 part4.2最短路徑問題-Dijkstra演算法

1.Dijkstra演算法介紹

演算法特點：

迪科斯徹演算法使用了廣度優先搜索解決賦權有向圖或者無向圖的單源最短路徑問題，演算法最終得到一個最短路徑樹。該演算法常用於路由演算法或者作為其他圖演算法的一個子模塊。

演算法的思路

Dijkstra演算法採用的是一種貪心的策略，聲明一個數組dis來保存源點到各個頂點的最短距離和一個保存已經找到了最短路徑的頂點的集合：T，初始時，原點 s 的路徑權重被賦為 0 （dis[s] = 0）。若對於頂點 s 存在能直接到達的邊（s,m），則把dis[m]設為w（s, m）,同時把所有其他（s不能直接到達的）頂點的路徑長度設為無窮大。初始時，集合T只有頂點s。 

然後，從dis數組選擇最小值，則該值就是源點s到該值對應的頂點的最短路徑，並且把該點加入到T中，OK，此時完成一個頂點， 

然後，我們需要看看新加入的頂點是否可以到達其他頂點並且看看通過該頂點到達其他點的路徑長度是否比源點直接到達短，如果是，那麼就替換這些頂點在dis中的值。 

然後，又從dis中找出最小值，重復上述動作，直到T中包含了圖的所有頂點。

2、Dijkstra演算法示例演示

我求下圖，從頂點v1到其他各個頂點的最短路徑.

首先第一步，我們先聲明一個dis數組，該數組初始化的值為：

我們的頂點集T的初始化為：T={v1}

既然是求 v1頂點到其餘各個頂點的最短路程，那就先找一個離 1 號頂點最近的頂點。通過數組 dis 可知當前離v1頂點最近是 v3頂點。當選擇了 2 號頂點後，dis[2]（下標從0開始）的值就已經從「估計值」變為了「確定值」，即 v1頂點到 v3頂點的最短路程就是當前 dis[2]值。將V3加入到T中。 

為什麼呢？因為目前離 v1頂點最近的是 v3頂點，並且這個圖所有的邊都是正數，那麼肯定不可能通過第三個頂點中轉，使得 v1頂點到 v3頂點的路程進一步縮短了。因為 v1頂點到其它頂點的路程肯定沒有 v1到 v3頂點短.

OK，既然確定了一個頂點的最短路徑，下面我們就要根據這個新入的頂點V3會有出度，發現以v3 為弧尾的有： < v3,v4 >,那麼我們看看路徑：v1–v3–v4的長度是否比v1–v4短，其實這個已經是很明顯的了，因為dis[3]代表的就是v1–v4的長度為無窮大，而v1–v3–v4的長度為：10+50=60，所以更新dis[3]的值,得到如下結果： 

因此 dis[3]要更新為 60。這個過程有個專業術語叫做「鬆弛」。即 v1頂點到 v4頂點的路程即 dis[3]，通過 < v3,v4> 這條邊鬆弛成功。這便是 Dijkstra 演算法的主要思想：通過「邊」來鬆弛v1頂點到其餘各個頂點的路程。

然後，我們又從除dis[2]和dis[0]外的其他值中尋找最小值，發現dis[4]的值最小，通過之前是解釋的原理，可以知道v1到v5的最短距離就是dis[4]的值，然後，我們把v5加入到集合T中，然後，考慮v5的出度是否會影響我們的數組dis的值，v5有兩條出度：< v5,v4>和 < v5,v6>,然後我們發現：v1–v5–v4的長度為：50，而dis[3]的值為60，所以我們要更新dis[3]的值.另外，v1-v5-v6的長度為：90，而dis[5]為100，所以我們需要更新dis[5]的值。更新後的dis數組如下圖： 

然後，我們使用同樣原理，分別確定了v6和v2的最短路徑，最後dis的數組的值如下： 

因此，從圖中，我們可以發現v1-v2的值為：∞，代表沒有路徑從v1到達v2。所以我們得到的最後的結果為：

Ⅱ 《選擇排序演算法分析及程序實現》教學案例:十大排序演算法

本節教學內容選自浙江教育出版社出版的《演算法與程序設計》。出於理論與實踐相結合的考慮，將教材第二章第三節的「排序」和第五章第三節的「排序演算法的程序實現」教學內容合並起來教學，以加深學生對演算法和程序設計的關系的體會。排序演算法是程序設計中的重要演算法，對它的學習既是對已經學過的三種程序設計結構的綜合運用，又能為後續對分查找的學習作好鋪墊。
一、教學目標
知識與技能：理解選擇排序演算法；能解釋冒泡排序、選擇排序的優勢；能由此及彼，歸納排序中的數字規律，探索更有效率的排序演算法；能在VB中規范地編寫程序。
過程與方法：在回顧冒泡排序演算法的過程中自然引出選擇排序，並以任務分解、逐級遞進的方式化解難點。以講授法和探究法相結合的方式，讓學生在自主探索中思考發現、歸納總結，逐步將排序方法用程序語言表達出來，最終實現程序，解決問題。
情感、態度與價值觀：培養學生對程序設計的興趣，激發學生探索新知的慾望和熱情，讓學生體會將自己的邏輯思維通過程序設計的方式實現的喜悅感和成就感。
二、學情分析
選擇排序演算法的學習是在學生學習了「冒泡排序」的基礎上進行的，而且學生對VB的基本語句、三種程序結構、數組變數、隨機數的生成，以及事件、過程等能較好地理解、應用，因此，程序界面的設計、無序的隨機數的生成、通用變數（n、數組變數）的定義等預備工作事先由教師准備。
三、教學重點、難點
教學重點：理解選擇排序演算法，以及演算法在VB中的實現。
教學難點：如何找到一組數中的最小數（或最大數），用來記錄最小值（或最大值）的變數t的初值為什麼是i，用來記錄查找的位置的循環變數j的初值與終值的確定。
四、素材准備
1.學生素材：Form1.frm
該窗體的程序界面如圖1所示，其中「自動生成數據」這一事件已能實現，「選擇排序」的代碼留空。
2.教師素材：PPT課件
五、教學過程
1.復習回顧，自然引出選擇排序
問題：若要將34、45、32、12、33這組數據按從小到大的順序進行冒泡排序，則需進行幾次冒泡排序，每次的排序結果分別是什麼，整個排序過程中進行了幾次數據交換，是否能減少交換次數？
設計意圖：復習冒泡排序演算法，並通過分析數據交換的次數，提問學生是否有辦法讓數據交換的次數變少，引發學生思考與發現，進而引出選擇排序演算法。
2.實例示範，初步了解選擇排序
教師以對四個無序整數進行遞增排序處理為例（假定數據已存放在數組中），簡要闡述選擇排序演算法。
第一遍：從第一個位置到最後一個位置中，找出最小值所在的位置，將該位置的值與第一個位置的值虧拿交換。
第二遍：從第二個位置到最後一個位置中，找出最小值所在的位置，將該位置的值與第二個位置的值交換。
依次類推，直到所有數都有序（如圖2）。
隨後，學生在了解選擇排序的基礎上完成以下課堂練習：
若要將34、45、32、12、33這一組數據按從小到大的順序進行選擇排序，則需進行幾次選擇排序，每次的排序結果分別是什麼，整個排序過程中進行了幾次數據交換？
學生在完成的過程中，與一開始對這組數據進行冒泡排序的過程進行比較，發現對這組數據來說，選擇排序的交換次數僅為三次，大大優於銷搭搭冒泡排序。
設計意圖：本部分僅對選擇排序作簡要闡述，枝數未對其中「如何找到最小數問題」進行具體說明，旨在讓學生先了解選擇排序演算法，對其有總體認識，樹立信心。
3.層層遞進，深入理解選擇排序
在學生初步了解選擇排序後，教師進而引導學生將選擇排序的每一遍排序分解為兩個步驟，即：
第一步：從位置1到位置n中，找到最小數的位置；若最小數不在位置1，則將最小數與位置1的數據進行交換。
第二步：從位置2到位置n中，找到最小數的位置；若最小數不在位置2，則將最小數與位置2的數據進行交換。
……
步驟分解後，接下來的關鍵是如何將這些步驟一一實現。教師以第一遍選擇排序為例，對演算法進行演示，具體如下：
先預設兩個變數：變數t和j。其中變數t用來記錄最小值所在的位置；變數j用來記錄查找的位置。
【演算法演示】
第一步：從位置1到位置4中，找到最小數的位置，具體過程如圖3所示。
【分析】第一遍選擇時，令記錄最小值所在的位置的初始值為1，即t=1。故將d(t)依次與d(2)、d（3）、d(4)進行比較，每次比較可描述為：
第一次：當 j=2時
如果d(t)>d(j)，則令t=j
第二次：當 j=3時
如果d(t)>d(j)，則令t=j
第三次：當 j=4時
如果d(t)>d(j)，則令t=j
經過這樣三次比較後，就完成了第一遍選擇排序。
【觀察】學生比較上述三次描述，發現j=2、3、4時，所執行的操作都是「如果d(t)>d(j)，則令t=j」，也就是說執行的是重復操作，繼而就想到了用循環語句來實現這個操作，也就是說，上面三次比較可整合為如下語句：
t=1
for j=2 to 4
如果d(t)>d(j)，則令t=j
Next j
第二步：若最小數不在位置1，則將最小數與位置1的數據進行交換。
這一步學生普遍較容易理解，教師給出偽代碼：如果t>1，則交換d(1)和d(t)。
此時，教師引導學生到教師事先分發的form1窗體中完成第一次選擇排序的程序代碼，並進行調試運行。
當然，調試運行過程中，學生會發現單擊「選擇排序」按鈕後，不能將排好序的數據輸出到列表框2中，隨後找到原因，將輸出語句補充完整。由於輸出語句學生已在冒泡排序中接觸過，故能自行完成。
當學生完成了第一遍選擇排序後，略有成就感，教師順勢提出第二遍選擇排序。理解了第一遍選擇排序，學生對第二遍、第三遍就不再那麼陌生了，理解起來也更容易了。教師簡單演示第二遍、第三遍選擇排序演算法後，學生便能在第一遍選擇排序的基礎上對代碼略作修改，完成第二遍、第三遍選擇排序的程序代碼。
設計意圖：分解問題難點，並能讓學生自己總結歸納出解決的辦法，既能落實知識點，又能激發學生的求知與探索慾望。
4.歸納總結，由特殊到一般
當學生通過三遍選擇排序完成了對四個數進行排序的操作時，便躍躍欲試，想要對更多的數進行排序，於是就開始找尋規律，他們會發現這三部分程序的主體大部分是相似的，只不過變數t與變數j的值有所變化。教師再繼續引導學生去找出變數t和變數j的變化規律。
為了便於學生更好地發現規律，教師在PPT上將三遍選擇的代碼放在一起，並將關鍵部分用紅色字體標出，如圖4所示。經過觀察、分析，學生得出第i遍選擇的程序代碼。
至此，選擇排序的核心代碼已基本完成，只要學生將變數i的范圍確定即可，而i的范圍即為選擇排序進行的遍數。這一點學生已經在一開始的演算法分析中明確了，即：如果有n個數，需進行的選擇遍數為n-1次。
故，學生可得出選擇排序代碼如下：
Fori= 1 to n-1
t = i
For j = i+1 to n
If d(t) > d(j) Thent=j
Next j
If t > i Then
temp = d(i)
d(i)=d(t)
d(t) = temp
End If
Next i
整個過程下來，演算法的基本框架以及程序的結構變得一目瞭然。
設計意圖：將選擇排序像剝洋蔥一樣一層層剝離，又慢慢地將其整合。整個過程中引導學生自己探索、發現規律、找尋方法，進而解決問題，不僅排除了學生對復雜演算法的畏懼感，同時還激發了學生的學習熱情。
5.調試運行，完成課堂任務
基本任務：學生先完成將一組數進行從小到大順序排序的程序調試。然後，修改程序，使其能將一組無序數據進行降序排列。
拓展任務：時間充裕的學生可以根據知識拓展內容比較冒泡排序和選擇排序的耗時，並在程序中體現出交換次數。
知識拓展：比較冒泡排序和選擇排序的消耗時間。
T1=timer (timer是取得當前時間的函數)
T2=timer
Label4.caption=「冒泡排序運行時間:」& t2-t1 &「秒」
設計意圖：通過由將一組數據進行遞增排序改為遞減排序，使學生明白程序中決定遞增或遞減的關鍵語句是什麼。而拓展任務則是為了給有能力的學生提供更多的學習機會和展示自我的平台。
（作者單位：浙江寧波市北侖中學）

Ⅲ 圖的相關演算法（二）：最小生成樹演算法

在含有n個頂點的連通圖中選擇n-1條邊，構成一棵極小連通子圖，並使該連通子圖中n-1條邊上權值之和達到最小，則稱其為連通網的最小生成樹。

例如，對於上圖中的連通網可以有多棵權值總和不相同的生成樹。

克魯斯卡爾（Kruskal）演算法，是用來求加權連通圖的最小生成樹的演算法。

基本思想 ：按照權值從小到大的順序選擇n-1條邊，並保證這n-1條邊不構成迴路。
具體做法 ：首先構造一個只含n個頂點的森林，然後依照權值從小到大從連通網中選擇邊加入到森林羨冊乎中，並使得森林不產生迴路，直到森林變成一棵樹為止。

以圖G4為例（更詳細的可以參考《演算法導論》p367），對Kruskal進行演示（假設，用數組R保存最小生成樹結果）。

第1步 ：將邊<E,F>加入R中。
邊<兄悉E,F>的權值最小，因此將它加入到最小生成樹結果R中。
第2步 ：將邊<C,D>加入R中。
上一步操作之後，邊<C,D>的權值最小，因此將它加入到最小生成樹結果R中。
第3步 ：將邊<D,E>加入R中。
上一步操作之後，邊<D,E>的權值最小，因此將它加入到最小生成樹結果R中。
第4步 ：將邊<B,F>加入R中。
上一步操作之後，邊<C,E>的權值最小，但<C,E>會和已有的邊構成迴路；因此，跳過邊<C,E>。同理，跳過邊<C,F>。將邊<B,F>加入到最小生成樹結果R中。
第5步 ：將邊<E,G>加入R中。
上一步操作之後，邊<E,G>的權值最小，因此將它加入到最小生成樹結果R中。
第6步 ：將邊<A,B>加入R中。
上一步操作之後，邊<F,G>的權值最小，但<F,G>會和已有的邊構成迴路；因此，跳過邊<F,G>。同理，跳過邊<B,C>。將邊<A,B>加入到最小生成樹結果R中。

此時，最小生成樹構造完成！它包括的邊依次是： <E,F> <C,D> <D,E> <B,F> <E,G> <A,B> 。

根據前面介紹的克魯斯卡爾演算法的基本思想和做法，我們能夠了解到，克魯斯卡爾演算法重點需要解決的以下兩個問題：
問題一 對圖的所有邊按照權值大小進行排序。
問題二 將邊添加到最小生成樹中時，怎麼樣判斷是否形成了迴路。

問題一用排序演算法排序即可。
問題二，處理方式：記錄頂點在「最小生成樹」中的終點，頂點的終點是「在最小生成樹中與它連通的最大頂點"(關於這一點，後面會通過圖片給出說明)。然後每次需要將一條邊添加到最小生成樹時，判斷該邊的兩個頂點的終點是否重合，重合的話則會構成迴路。 以下圖來進行說明：

在將<E,F> <C,D> <D,E>加入到最小生成樹R中之後，這幾條邊的頂點就都有了終點：

關於終點，姿跡就是將所有頂點按照從小到大的順序排列好之後；某個頂點的終點就是"與它連通的最大頂點"。 因此，接下來，雖然<C,E>是權值最小的邊。但是C和E的重點都是F，即它們的終點相同，因此，將<C,E>加入最小生成樹的話，會形成迴路。這就是判斷迴路的方式。

普里姆（Prim）演算法，也是求加權連通圖的最小生成樹的演算法。

基本思想
對於圖G而言，V是所有頂點的集合；現在，設置兩個新的集合U和T，其中U用於存放G的最小生成樹中的頂點，T存放G的最小生成樹中的邊。從所有的 uЄU ，vЄ(V-U)（V-U表示除去U的所有頂點）的邊中選取權值最小的邊（u，v），將頂點v加入U中，將邊（u,v）加入集合T中，如此不斷重復，直到U=V為止，最小生成樹構造完畢，此時集合T中包含了最小生成樹中的所有邊。

以上圖G4為例，來對普里姆進行演示(從第一個頂點A開始通過普里姆演算法生成最小生成樹)。

初始狀態 ：V是所有頂點的集合，即V={A,B,C,D,E,F,G}；U和T都是空！
第1步 ：將頂點A加入到U中。
此時，U={A}。
第2步 ：將頂點B加入到U中。
上一步操作之後，U={A}, V-U={B,C,D,E,F,G}；因此，邊(A,B)的權值最小。將頂點B添加到U中；此時，U={A,B}。
第3步 ：將頂點F加入到U中。
上一步操作之後，U={A,B}, V-U={C,D,E,F,G}；因此，邊(B,F)的權值最小。將頂點F添加到U中；此時，U={A,B,F}。
第4步 ：將頂點E加入到U中。
上一步操作之後，U={A,B,F}, V-U={C,D,E,G}；因此，邊(F,E)的權值最小。將頂點E添加到U中；此時，U={A,B,F,E}。
第5步 ：將頂點D加入到U中。
上一步操作之後，U={A,B,F,E}, V-U={C,D,G}；因此，邊(E,D)的權值最小。將頂點D添加到U中；此時，U={A,B,F,E,D}。
第6步 ：將頂點C加入到U中。
上一步操作之後，U={A,B,F,E,D}, V-U={C,G}；因此，邊(D,C)的權值最小。將頂點C添加到U中；此時，U={A,B,F,E,D,C}。
第7步 ：將頂點G加入到U中。
上一步操作之後，U={A,B,F,E,D,C}, V-U={G}；因此，邊(F,G)的權值最小。將頂點G添加到U中；此時，U=V。

此時，最小生成樹構造完成！它包括的頂點依次是：A B F E D C G。

Ⅳ 題目1:一個簡單的演算法演示程序(JAVA語言實現)

1. 選擇一個演算法（提供選擇見下），利用各種方法（圖形、動畫等）演示演算法的演示過程。
2. 可以進行手動演示，也可以自動步進式演示。
3. 允許用戶設置演算法的各個輸入參數，以及自動步進式演示中的時間間隔。
4. 不同的演算法輸入要求見下。
界面要求：
1. 盡量使用圖形界面實現，要符合日常軟體使用規范來設計菜單和界面。
2. 如果無法實現圖形界面，則在命令行方式下也需要提供菜單，方便用戶操作。
其他要求：
1. 標識符命名遵循Windows命名規范。
2. 能夠注意各種異常處理，注重提高程序運行效率。
提交內容：
1. 全部源代碼。
2. 軟體設計和使用說明書（UML類圖；實現的功能、主要技術；使用幫助文檔）
參考演算法：
1. 最小生成樹演算法：Prim演算法、Kruskal演算法。允許以下方式輸入一個圖形：繪制圖形、輸入鄰接矩陣、輸入邊及其關聯的頂點。要求在圖形方式下進行演示演算法執行步驟。
2. 單源最短路演算法：Dijkstra演算法。允許以下方式輸入一個圖形：繪制圖形、輸入鄰接矩陣、輸入邊及其關聯的頂點。要求在圖形方式下進行演示演算法執行步驟。
3. 最優編碼演算法：Huffman編碼演算法。允許用戶輸入一段英文文字，或者打開一個txt文檔（英文內容），據此文檔內容進行編碼。要求動態列出每個字元的出現概率統計結果以及對應編碼。
4. 其他可供演示的具有一定難度的演算法，如關鍵路徑問題、有向圖的極大連通分支等。

Ⅳ 經典筆試面試知識整理，數據結構與演算法(代碼演示)

題目描述：

在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

輸入描述: array： 待查找的二維數組 target：查找的數字

輸出描述:

查找到返回true，查找不到返回false

題目描述：

請實現一個函數，將漏祥一個字元串中的空格替換成「%20」。例如，當字元串為We Are Happy.則經過替換之後的字元串為We%20Are%20Happy。

題目描述： 輸入一個鏈表，從尾到頭列印鏈表每個節點的值。

輸入描述： 輸入為鏈表的表頭

輸出描述： 輸出為需要列印的「新鏈表」的表頭

題目描述：

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。

例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹並返回。

題目描述：

把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一喊搜鉛個旋轉，輸出旋轉數組的最小元素。

例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大於0，若數組大小為0，請返回0。

1、題目描述：

大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項。n<=39

2、題目描述：

一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法。

3、題目描述：

一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。

4、題目描述：

我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？

1、題目描述：

輸入一個整數，輸出該數二進製表示中1的個數。其中負數用補碼表示。

2、題目描述：

給定一個double類型的浮點數base和int類型的整數exponent。求base的exponent次方。

題目描述：

輸入一個整數數組，實現一個函數來調整鄭好該數組中數字的順序，使得所有的奇數位於數組的前半部分，所有的偶數位於位於數組的後半部分，並保證奇數和奇數，偶數和偶數之間的相對位置不變。

題目描述：

用兩個棧來實現一個隊列，完成隊列的Push和Pop操作， 隊列中的元素為int類型。

題目描述：

輸入一個鏈表，輸出該鏈表中倒數第k個結點。

Ⅵ 對給定的網和起點，實現求解最小生成樹的PRIM演算法，並給出動態演示。萬分火急

最近忙著考試，沒時間做圖形界面來動態演示部分啦，先給你一個基本的Prim程序吧，希望有所幫助。
/**
* PRIM(簡單版) 最小生成樹演算法 (Minimum Spanning Tree)
* 輸入：圖g； // 有向圖或者無向圖
* 輸出：(1)最小生成樹長sum；
* (2)最小生成樹prev。
* 結構: 圖g用鄰接矩陣表示，最短邊長dist用數組表示。
* 演算法：Prim演算法
* 復雜度：O(|V|^2)
*/
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

int n; // n : 頂點個數
vector<vector<int> > g; // g : 圖(graph)(用鄰接矩陣(adjacent matrix)表示)
vector<bool> known; // known : 各點是否已經選取
vector<早擾int> dist; // dist : 已選取點集到凳枯未選取點的最小邊長
vector<int> prev; // prev : 最小生成樹中各點的前一頂點
int s; // s : 起點(start)
int sum; // sum : 最小生成樹長

bool Prim() // 貪心演算法(Greedy Algorithm)
{
known.assign(n, false);
dist.assign(n, INT_MAX);
prev.resize(n); // 初始化known、dist、prev。
dist[s] = 0; // 初始化起點到自身的路徑長為0。
int i;
for (i = 0; i < n; ++i)
{
int min = INT_MAX, v;
for (int i = 0; i <陸粗旦 n; ++i)
if (!known[i] && min > dist[i])
min = dist[i], v = i; // 尋找未知的最短路徑長的頂點v，
if (min == INT_MAX) break; // 如果找不到，退出；
known[v] = true; // 如果找到，將頂點v設為已知，
sum += dist[v]; // 調整最小生成樹長
for (int w = 0; w < n; ++w) // 遍歷所有v指向的頂點w，
if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])
dist[w] = g[v][w], prev[w] = v; /* 調整頂點w的最短路徑長dist和最短路徑的前一頂點 prev。 */
}
return i == n; // 如果選取頂點個數為n，成功。
}

int main()
{
n = 7;
g.assign(n, vector<int>(n, INT_MAX));
g[0][1] = g[1][0] = 2; g[0][2] = g[2][0] = 4; g[0][3] = g[3][0] = 1;
g[1][3] = g[3][1] = 3; g[1][4] = g[4][1] = 10;
g[2][3] = g[3][2] = 2; g[2][5] = g[5][2] = 5;
g[3][4] = g[4][3] = 7; g[3][5] = g[5][3] = 8; g[3][6] = g[6][3] = 4;
g[4][6] = g[6][4] = 6;
g[5][6] = g[6][5] = 1;

s = 0; // 起點任選
sum = 0;
if (Prim())
{
cout << sum << endl;
for (int i = 1; i < n; ++i)
if(i != s) cout << prev[i] << "->" << i << endl;
}
else
{
cout << "Some vertex cann't be reached." << endl;
}

system("pause");
return 0;
}