cc語言貪心算法ppt課件-資料下載頁
2025-05-05 12:00本頁面
【正文】 形，可以只使用下三角或上三角，在此使用下三角部分，即 ij的部分。 演示算法實現(xiàn)過程。 人工模擬 1 2 3 4 5 5 5 6 6 6 最小生成樹的耗費為 15 算法難點 從剛才的演示過程，可知算法實現(xiàn)有兩個難點： （ 1）邊的選擇要求從小到大選擇，則開始顯然要對邊進行 升序排序 。 （ 2）選擇的邊是否需要，則從判斷該邊加入后是否構(gòu)成環(huán) 入手。 難點解決（一） （ 1）對邊升序排序 方法可根據(jù)以前 《 數(shù)據(jù)結(jié)構(gòu) 》 中選擇合適的排序。 在此采用鏈式結(jié)構(gòu)，通過插入排序完成。 每一結(jié)點存放一條邊的 左右端點序號、權(quán)值及后繼結(jié)點指針 。 難點解決（二） （ 2）邊的加入是否構(gòu)成環(huán) 一開始假定各頂點分別為 一組 ，其組號為端點序號。 選擇某邊后，看其兩個端點是否在同一組中，即所在組號是否相同，如果是，表示構(gòu)成了環(huán)，則舍去。 如果兩個端點所在的組不同，則表示可以加入，則將該邊兩端的組 合并 成同一組。 貪心算法 最小生成樹代碼
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1