貪婪算法——Prim 算法

在實踐中常常會遇到這樣的問題：給定n人點，把它們按照一種代價最低的方式連接配接起來，使得任意兩點之間都存在一條路徑。

這樣的問題可應用在各類網絡的設計，包括通信網絡、計算機網絡、交通網絡以及輸電網絡，進而能夠以最低的成本實作網絡聯通。另外，它也有助于構造旅行商等難題的近似解。

定義：通圖的一棵生成樹是包含圖中的所有頂點的連通無環子圖（也就是一棵樹）。權重連通圖的一棵最小生成樹是圖的一棵權重最小的生成樹，其中，樹的權重定義為所有邊的權重總和。最小生成樹問題就是求一個給定的權重連通圖的最小生成樹問題。

根據上圖構造如下表格：

頂點	a	b	c	d	e	f
a	INF	3	INF	INF	6	5
b	3	INF	1	INF	INF	4
c	INF	1	INF	6	INF	5
d	INF	INF	6	INF	8	5
e	6	INF	INF	8	INF	2
f	5	4	4	5	2	INF

#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0xFFFFFFFF   //INF代表兩點之間不可達
#define n 6  //頂點數量
char v[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; //頂點
struct node
{
    int data;   //頂點資料
    unsigned int lowestcost;  //最低成本
}closedge[n]; //Prim算法中的輔助資訊
typedef struct
{
    int u;
    int v;//頂點
    unsigned int cost;  //邊的代價
}Arc;  //原始圖的邊資訊
void initialization(int adjMat[][n])  //初始化 鄰接矩陣表示法
{
    for (int i = 0; i < n; i++)   //初始化鄰接矩陣，假設所有頂點皆為不可達
        for (int j = 0; j < n; j++)
        {
            adjMat[i][j] = INF;
        }
       //将圖中可抵達的頂點指派，根據上面的截圖表格進行初始化
    adjMat[0][1] = 3; adjMat[0][4] = 6; adjMat[0][5] = 5;
    adjMat[1][0] = 3; adjMat[1][2] = 1; adjMat[1][5] = 4;
    adjMat[2][1] = 1; adjMat[2][3] = 6; adjMat[2][5] = 5; 
    adjMat[3][2] = 6; adjMat[3][4] = 8; adjMat[3][5] = 5;
    adjMat[4][0] = 6; adjMat[4][3] = 8; adjMat[4][5] = 2;
    adjMat[5][0] = 5; adjMat[5][1] = 4; adjMat[5][2] = 4;adjMat[5][3] = 5;adjMat[5][4] = 2;
}
int Minmum(struct node * closedge)  //傳回最小代價邊
{
    unsigned int min = INF;
    int index = -1;
    for (int i = 0; i < n;i++) //循環周遊，找到最小邊代價傳回
    {
        if (closedge[i].lowestcost < min && closedge[i].lowestcost !=0)
        {
            min = closedge[i].lowestcost;
            index = i;
        }
    }
    return index;
}
void MiniSpanTree_Prim(int adjMat[][n], int s)  //Prim算法實作最小生成樹
{
    for (int i = 0; i < n;i++)
    {
        closedge[i].lowestcost = INF;
    }     
    closedge[s].data = s;      //從頂點s開始
    closedge[s].lowestcost = 0;
    for (int i = 0; i < n;i++)  //初始化輔助數組
    {
        if (i != s)
        {
            closedge[i].data = s;
            closedge[i].lowestcost = adjMat[s][i];
        }
    }
    for (int e = 1; e <= n -1; e++)  //n-1條邊時退出
    {
        int k = Minmum(closedge);  //選擇最小代價邊
        cout << v[closedge[k].data] << "--" << v[k] << endl;//加入到最小生成樹
        closedge[k].lowestcost = 0; //代價置為0
        for (int i = 0; i < n;i++)  //更新v中頂點最小代價邊資訊
        {
            if ( adjMat[k][i] < closedge[i].lowestcost)
            {
                closedge[i].data = k;
                closedge[i].lowestcost = adjMat[k][i];
            }
        }
    }
}
 
int main()
{
    int  adjMat[n][n] = {0};
    initialization(adjMat);   //初始化
	cout<<"最小生成樹的邊為："<<endl;
    MiniSpanTree_Prim(adjMat,0); //Prim算法，從s=1開始.
    return 0;
}