dbs第十章ppt課件-資料下載頁
2025-05-05 12:08本頁面
【正文】 正在構(gòu)造中的生成樹。初始狀態(tài)下，這棵生成樹只有一個頂點，沒有邊，即 V’={u0}， E’={ }， u0是任意選定的起始頂點。 從初始狀態(tài)開始，重復(fù)執(zhí)行下列運算： 在所有 u?V’， v?VV’的邊 (u,v)， (u,v)?E中找一條代價最小的邊 (u’,v’)， 邊 (u’,v’)并入集合 E’，將頂點 v’并入集合 V’。 直到 V=V’為止。 這時 E’中必有 n1條邊， T=(V’,E’)是圖 G的一棵最小代價生成樹。 （ Prim) 普里姆算法 (u’,v’)的含義是： 一端在樹上，另一端不在樹上的最小權(quán)值邊 0 3 1 2 4 5 3 6 6 6 5 5 5 4 2 1 圖 1015 普里姆算法構(gòu)造最小代價生成樹的過程 1 圖 G 構(gòu)造中的最小代價生成樹 T 普里姆算法演示 為實現(xiàn) Prim算法 ,定義兩個一維數(shù)組 ,用于存放中間構(gòu)造過程和最終結(jié)果。 ? nearest ? lowcost 設(shè) v是當(dāng)前尚未選入生成樹的頂點， nearest[v]中保存邊(u, v)在 生成樹上 的那個頂點 u，邊 (u, v)是所有 u ? V’的 邊中 權(quán)值最小 的邊。 u v u 1 0 3 8 7 6 5 5 nearest 0 1 … v … n lowcost V’ nearest[v] 定義一個一維數(shù)組 mark，用于表示某個頂點是否在生成樹上。 如果 mark[v]=false,表示 v未加入生成樹 ，反之， v已選入。 初始時： nearest[v]=1,lowcost[v]=MaxNum, mark[v]=FALSE (nearest[v],v,lowcost[v])代表一條權(quán)值為 lowcost[v]，兩個頂點分別為 nearest[v]和 v的一條邊 (nearest[v],v)。 如（ 2， 1， 5） : 邊 (2,1)的代價為 5， 其中 nearest[1]=2； lowcost[1]=5 它記錄當(dāng)前對 v而言，與 生成樹上頂點相鄰的所有邊中權(quán)值最小者 。 0 3 1 2 4 5 3 6 6 6 5 5 5 4 2 1 1 2 3 4 5 0 1 ∞ nearest lowcost 1 1 ∞ 2 1 ∞ 3 1 ∞ 4 1 ∞ 5 1 ∞ 6 1 5 50 0 0 0 6 4 2 32 2 5 2 0 0 1V’ VV’ 0 2 5 3 1 4 普里姆算法的 C語言程序 (【 程序 10－ 10】 )。 void Prim(Graph g, int k, int *nearest, T* lowcost) { int i, j, min, n=。 BOOL mark[MaxVertices]。 ENode *p。 if (k0 || kn－ 1){ printf(BadInput\n)。 return 。 } for (i=0。 in。 i++){ /* 初始化 */ nearest[i]=－ 1。 mark[i]=FALSE。 lowcost[i]=MaxNum。 } 程序的時間復(fù)雜度： O(n2) lowcost[k]=0。 nearest[k]=k。 mark[k]=TRUE。 for (i=1。 in。 i++) { for( p=[k]。 p。 p=pNextArc) { j= pAdjVex。 if (( !mark[j] )amp。amp。( lowcost[j] pW )){ lowcost[j]=pW。 nearest[j]=k。 } } min=MaxNum。 for (j=0。 jn。 j++) if ((!mark[j])amp。amp。(lowcost[j]min)){ min=lowcost[j]。 k=j。 } mark[k]=TRUE。 } } 修改 lowcost和nearest的值 求下一條最小權(quán)值的邊 將頂點 k加到生成樹上 將 源 點 k加入到生成樹上 畫出給定圖的最小的生成樹，要求從頂點 1出發(fā)。 1 3 2 5 4 7 6 8 5 15 3 10 12 2 7 9 6 1 3 2 7 4 6 5 5 3 7 2 6 15 瀏覽 查詢 刪除 插入 創(chuàng)建空表 選擇要進(jìn)行的操作 插入學(xué)生記錄 刪除學(xué)生記錄 查詢學(xué)生記錄 顯示所有學(xué)生記錄 退出程序 主程序： 循環(huán)語句 調(diào)用 PrintElements函數(shù)，顯示表中所有記錄 顯示主菜單 鏈接表示需要清空鏈表 Clear(amp。lst)。 實驗： 插入學(xué)生記錄：函數(shù) InsertRecord: 輸入學(xué)生信息 調(diào)用 Search_Insert函數(shù) 將學(xué)生記錄插入有序表 順序表 鏈接表示 插入函數(shù) InsertRecord: 輸入學(xué)生信息 調(diào)用 Search_Insert函數(shù) 將學(xué)生記錄插入有序表 Search_Insert函數(shù) 查找到插入點的前驅(qū)結(jié)點 生成新結(jié)點 插入到前驅(qū)結(jié)點后面 插入學(xué)生記錄 刪除函數(shù) RemoveRecord: 顯示 刪除記錄 調(diào)用 PrintElements函數(shù) 顯示有序表中所有學(xué)生信息 輸入要刪除的記錄序號 調(diào)用 Remove函數(shù) 刪除 學(xué)生記錄 刪除成功 y 順序表中的運算 順序表 刪除函數(shù) RemoveRecord: 顯示 刪除記錄 調(diào)用 PrintElements函數(shù) 顯示有序表中所有學(xué)生信息 輸入要刪除的記錄序號 調(diào)用 Remove函數(shù) 刪除 學(xué)生記錄 刪除成功 y 鏈接表示 刪除學(xué)生記錄 順序搜索有序表。 查詢函數(shù) Search: 顯示記錄 輸入要查詢的學(xué)號 調(diào)用 SeqSearch2函數(shù)在有序表中查詢學(xué)生記錄 成功 y 順序表 查詢函數(shù) Search: 顯示記錄 輸入要查詢的學(xué)號 在有序表中查詢學(xué)生記錄 成功 y 鏈接表示 查詢學(xué)生記錄 typedef int KeyType。 struct student { KeyType Key。 //學(xué)號 關(guān)鍵字 char name[20]。 char sex。 int age。 }。 typedef struct student T。 typedef struct list{ int Size, MaxList。 T Elements[MaxSize]。 } List。 //順序表 typedef int KeyType。 struct student { KeyType Key。 //學(xué)號 關(guān)鍵字 char name[20]。 char sex。 int age。 }。 typedef struct student T。 typedef struct node{ T Element。 struct node* Link。 } Node。 typedef struct list{ Node * First。 int Size。 } List。 鏈接表示
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1