最小花費擴張樹 minimum (cost) spanning tree.pptxVIP

101北一女中資訊選手培訓營;Minimum Cost;Tree的性質;;問題始源;;特性觀察;特性觀察;特性觀察;簡單的方向：Greedy;Algorithm I :  Prim’s Algorithm;Prim’s Algorithm;Prim’s Algorithm;;;;範例;範例;範例;範例;演算法描述;其他一些處理;另外要注意的;#include string.h // 為了用memset這個function所以要include這個 #define INF 2147483647 // 用int的最大值做為無限大 int graph[N][N]; // 假設我們有N個點。這裡存的是邊(i,j)的花費(無向邊) // 沒有邊時的花費就是INF int cost[N]; // 記錄目前要把第i個點加入正確聯盟所需要的花費 int last[N]; // 記錄第i個點是透過誰加入了正確聯盟(等於是存在edge(last[i], i)) int choosed[N]; // 記錄是否已經加入了正確聯盟 int fin_cnt; // 記錄已經加入正確聯盟的點的個數 int total_cost; // 記錄總花費 void init(){ // 初始化 // memset會把整塊記憶體空間都填上零，有歸零作用(但不能用來歸成除了0和-1之外的其他值)。 memset(choosed, 0, sizeof(choosed)); // last = -1代表自己就是root，一開始所有點都是自己的root memset(last, -1, sizeof(last)); // 以idx=0的點作為root開始看花費 cost[0] = 0; choosed[0] = 1; int i; for ( i = 1 ; i N ; i++ ){ cost[i] = graph[0][i]; // 如果有邊cost就會是該條邊，反之則會是INF if ( cost[i] != INF ) last[i] = 0; } fin_cnt = 1; // 一開始只有一個點在正確聯盟裡 } ;void prim(){ int min; // 用來存這一輪找到的花費最小值 int min_idx; // 用來存這一輪找到花費最小的是哪個點 int i; while ( fin_cnt N ) { // 如果小於N代表還沒找完 min = INF; // 初始化成INF，用來找最小值 min_idx = -1; // 初始化成-1，之後用來判別有沒有找到新的可用的點 for ( i = 1 ; i N ; i++ ){ // 跑過所有點，找最小值 if ( choosed[i] == 1 ) // 已經在正確聯盟裡就不考慮 continue; if ( cost[i] min ){ min_idx = i; min = cost[i]; } } if ( min_idx == -1 ) break; // 如果沒找到代表此圖找不到spanning tree choosed[min_idx] = 1; // 標記min_idx這個點進入了正確聯盟 total_cost += cost[min_idx]; // 加上加入這個點的cost fin_cnt++; // fin_cnt增加一，代表多了一個點已經確定 // 看看還沒有被選的點，有沒有點能夠透過min_idx