基本思想
最小生成樹(Minimum cost Spanning Tree)
構(gòu)造連通圖的最小代價生成樹稱為最小生成樹---《大話數(shù)據(jù)結(jié)構(gòu)》
通俗來說就是尋找權(quán)值最小的路徑集合來連接圖中所有的節(jié)點(diǎn)您访。
prim算法
- 將起始點(diǎn)(可以是圖中的任意節(jié)點(diǎn))加入集合G.
- 從圖中尋找到G最短的路徑锡凝，加入路徑集合T. 并把路徑的終點(diǎn)加入集合G.
- 重復(fù)步驟2叼架，知道G中包含所有的點(diǎn) or T中邊數(shù)量=點(diǎn)的數(shù)量-1.
為了實現(xiàn)此算法翰守，我們需要定義幾個變量
- 保存剩余節(jié)點(diǎn)到G的最短距離的集合lowcost
int lowcost[num] //下標(biāo)為外部的點(diǎn)剃诅，值為到G的距離
- 保存lowcost中每個邊連接到G中的哪一個節(jié)點(diǎn)的節(jié)點(diǎn)集合
int adjvex[num] //下標(biāo)為外部的點(diǎn)送挑，值為G中的點(diǎn)
代碼是在大話數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上修改的--現(xiàn)在能從任意節(jié)點(diǎn)開始
圖的初始化為
for (int i = 0; i < this->num; i++) {
for (int j = 0; j < this->num; j++) {
if (i == j) {
this->array[i * num + j] = 0;
} else {
this->array[i * num + j] = 65535;
};
}
}
下面是算法實現(xiàn)
void MyGraph::primTree(int node_index) {
int min, i, j, k, MAXVELUE = 65535;
//保存最短邊的起始點(diǎn)，下標(biāo)為外部的點(diǎn)金麸，值為當(dāng)前生成樹中的點(diǎn)
int adjvex[this->num];
//保存各頂點(diǎn)到當(dāng)前最小生成樹的距離(權(quán)值)逃延，下標(biāo)為外部的點(diǎn)览妖，值為到當(dāng)前生成樹的距離
int lowcost[this->num];
//將和起始點(diǎn)相關(guān)的點(diǎn)之間的權(quán)值加入,并設(shè)置起始點(diǎn)為node_index處的點(diǎn)
for (i = 0; i < this->num; i++) {
lowcost[i] = this->array[node_index * num + i];
adjvex[i] = node_index;
}
//循環(huán)剩下的點(diǎn)
for (i = 0; i < this->num; i++) {
if (i != node_index) {
min = MAXVELUE;
j = 0;
k = 0;
/* 循環(huán)全部頂點(diǎn) 選擇最小值*/
while (j < this->num) {
if (lowcost[j] != 0 && lowcost[j] < min) {
/* 當(dāng)前權(quán)值成為最小值 */
min = lowcost[j];
/* 將當(dāng)前最小值的下標(biāo)存入k */
k = j;
}
j++;
}
cout << "bian: (" << this->node_array[adjvex[k]].data << "," << this->node_array[k].data << ")" << endl;
/* 將當(dāng)前頂點(diǎn)的權(quán)值設(shè)置為0,表示此頂點(diǎn)已經(jīng)加入生成樹豪華套餐 */
lowcost[k] = 0;
//重新計算剩余點(diǎn)到生成樹的距離
for (j = 0; j < this->num; j++) {
/* 如果下標(biāo)為k頂點(diǎn)各邊權(quán)值小于此前這些頂點(diǎn)到達(dá)生成樹的最短距離 */
if (lowcost[j] != 0 && this->array[k * this->num + j] < lowcost[j]) {
/* 將較小的權(quán)值存入lowcost相應(yīng)位置 */
lowcost[j] = this->array[k * this->num + j];
/* 將當(dāng)前最短邊的起始點(diǎn)置為k */
adjvex[j] = k;
}
}
}
}
}
運(yùn)行例子中的圖為
最小生成樹.jpg --圖來自慕課網(wǎng)視頻
以節(jié)點(diǎn)B開始，最終輸出為
prim結(jié)果.png
