基本思想

最小生成樹(shù)(Minimum cost Spanning Tree)

構(gòu)造連通圖的最小代價(jià)生成樹(shù)稱為最小生成樹(shù)---《大話數(shù)據(jù)結(jié)構(gòu)》
通俗來(lái)說(shuō)就是尋找權(quán)值最小的路徑集合來(lái)連接圖中所有的節(jié)點(diǎn)。

prim算法

1. 將起始點(diǎn)(可以是圖中的任意節(jié)點(diǎn))加入集合G.
2. 從圖中尋找到G最短的路徑，加入路徑集合T. 并把路徑的終點(diǎn)加入集合G.
3. 重復(fù)步驟2，知道G中包含所有的點(diǎn) or T中邊數(shù)量=點(diǎn)的數(shù)量-1.

為了實(shí)現(xiàn)此算法，我們需要定義幾個(gè)變量

• 保存剩余節(jié)點(diǎn)到G的最短距離的集合lowcost

 int lowcost[num]  //下標(biāo)為外部的點(diǎn)，值為到G的距離

• 保存lowcost中每個(gè)邊連接到G中的哪一個(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)開(kāi)始

圖的初始化為

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;
            };
        }
    }

下面是算法實(shí)現(xiàn)

void MyGraph::primTree(int node_index) {
    int min, i, j, k, MAXVELUE = 65535;
    //保存最短邊的起始點(diǎn)，下標(biāo)為外部的點(diǎn)，值為當(dāng)前生成樹(shù)中的點(diǎn)
    int adjvex[this->num];
    //保存各頂點(diǎn)到當(dāng)前最小生成樹(shù)的距離(權(quán)值)，下標(biāo)為外部的點(diǎn)，值為到當(dāng)前生成樹(shù)的距離
    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)加入生成樹(shù)豪華套餐 */
            lowcost[k] = 0;
            //重新計(jì)算剩余點(diǎn)到生成樹(shù)的距離
            for (j = 0; j < this->num; j++) {
                /* 如果下標(biāo)為k頂點(diǎn)各邊權(quán)值小于此前這些頂點(diǎn)到達(dá)生成樹(shù)的最短距離 */
                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)行例子中的圖為

最小生成樹(shù).jpg --圖來(lái)自慕課網(wǎng)視頻

以節(jié)點(diǎn)B開(kāi)始，最終輸出為

prim結(jié)果.png