普里姆算法和迪克斯特拉算法的比較

對(duì)比是非常有效的學(xué)習(xí)方法。普里姆算法和迪克斯特拉算法是數(shù)據(jù)結(jié)構(gòu)中的典型算法，本文通過它們的設(shè)計(jì)和實(shí)現(xiàn)的對(duì)比，展示這種方法的意義。

1基本思想和數(shù)學(xué)描述比較

對(duì)一個(gè)連通網(wǎng)絡(luò)即無向加權(quán)連通圖，其權(quán)值總和最小的生成樹稱為最小生成樹。對(duì)一個(gè)有向網(wǎng)絡(luò)和一個(gè)稱為源點(diǎn)的頂點(diǎn)，求源點(diǎn)到其余各頂點(diǎn)的最短帶權(quán)路徑，稱為單源最短路徑。

普里姆(Prim)算法和迪克斯特拉(Dijkstra)算法分別是求最小生成樹和單源最短路徑的算法，它們的基本思想和數(shù)學(xué)描述對(duì)比見表1和表2。

2步驟和圖示比較

為了實(shí)現(xiàn)普里姆算法，首先引入一個(gè)結(jié)構(gòu)PathData來記錄候選邊信息，入選子網(wǎng)頂點(diǎn)作為始點(diǎn)，候選集頂點(diǎn)作為終點(diǎn)。其實(shí)無向網(wǎng)絡(luò)的邊是不分始點(diǎn)和終點(diǎn)的，這樣做僅是為了表述方便。

下面以圖1(b)為例，詳細(xì)介紹普里姆算法的實(shí)現(xiàn)步驟：

(1) 由始點(diǎn)0組成入選子網(wǎng)，其余頂點(diǎn)組成候選集。用無色環(huán)表示入選子網(wǎng)的頂點(diǎn)，有色環(huán)表示候選集頂點(diǎn)，虛線表示候選邊，權(quán)M代表一個(gè)很大的值(這個(gè)值應(yīng)該大于該網(wǎng)絡(luò)的所有權(quán)之和)，表示對(duì)應(yīng)的候選邊不存在(這樣做是為了計(jì)算方便)。把候選邊集存入PathData結(jié)構(gòu)數(shù)組。如圖1(c)所示。

(2) 在候選邊集中選定一條權(quán)最小的候選邊加到入選子網(wǎng)(用實(shí)線表示)。快速實(shí)現(xiàn)的方法是將候選邊集調(diào)整為小根堆，小根堆首元素就是最小的候選邊。如圖1(d)所示。

(3) 更新候選邊集(虛線)：如果最小候選邊存在，計(jì)算器加1，表示正式加到入選子網(wǎng)。然后，對(duì)新候選集的每一個(gè)頂點(diǎn)，它原來對(duì)應(yīng)的候選邊和入選集新的頂點(diǎn)與它的關(guān)聯(lián)邊比較，取小者，作為它對(duì)應(yīng)的新候選邊。……