快捷導(dǎo)航

C++示例詳解Prim算法與優(yōu)先隊列

更新時間：2022年06月30日 09:47:32 作者：成就一億技術(shù)人

這篇文章介紹了C++ Prim算法、優(yōu)先隊列，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下

最小生成樹的最優(yōu)子結(jié)構(gòu)性質(zhì)：假設(shè)一個無向圖包含兩部分A,B，其中A為最小生成樹部分，B為剩余部分，則存在以下性質(zhì)：該無向圖中一個頂點在A部分，另一個頂點在B部分的邊中，權(quán)值最小的邊一定屬于整個無向圖的最小生成樹，即部分最小權(quán)值是整個最小生成樹的局部最有解，該性質(zhì)符合貪心算法的特點。

Prim算法

基于最小生成樹的該性質(zhì)，使用prim算法來求解最小生成樹。

貪心算法屬性：一個局部全優(yōu)解，也是全局全優(yōu)解

思想：設(shè)T是最小生成樹，A<=V,(u,v)是連接著A到A補集（一個在A中，一個不在A中）最小權(quán)值的邊，則一定是最小生成樹邊。

prim代碼實現(xiàn)

#include <stdio.h>
#include <malloc.h>
#define VERTEXNUM 6
void createGraph(int (*edge)[VERTEXNUM], int start, int end, int value);
void displayGraph(int (*edge)[VERTEXNUM]);
void prim(int (*edge)[VERTEXNUM], int (**tree)[VERTEXNUM], int startVertex, int* vertexStatusArr);
int main(void){
	//動態(tài)創(chuàng)建存放邊的二維數(shù)組  
        int (*edge)[VERTEXNUM] = (int (*)[VERTEXNUM])malloc(sizeof(int)*VERTEXNUM*VERTEXNUM);
        int i,j;
        for(i=0;i<VERTEXNUM;i++){
                for(j=0;j<VERTEXNUM;j++){
                        edge[i][j] = 0;
                }
        }
	//存放頂點的遍歷狀態(tài)，0：未遍歷，1：已遍歷 
        int* vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM);
        for(i=0;i<VERTEXNUM;i++){
                vertexStatusArr[i] = 0;
        }
        printf("after init:\n");
        displayGraph(edge);
	//創(chuàng)建圖  
        createGraph(edge,0,1,6);
        createGraph(edge,0,3,5);
        createGraph(edge,0,2,1);
        createGraph(edge,1,2,5);
        createGraph(edge,1,4,3);
        createGraph(edge,2,4,6);
        createGraph(edge,2,3,5);
        createGraph(edge,2,5,4);
        createGraph(edge,3,5,2);
        createGraph(edge,4,5,6);
        printf("after create:\n");
        displayGraph(edge);
	//最小生成樹
        int (*tree)[VERTEXNUM] = NULL;
        prim(edge, &tree, 0, vertexStatusArr);
        printf("after generate tree:\n");
        displayGraph(tree);
        free(edge);
        free(tree);
        return 0;
}
//創(chuàng)建圖
void createGraph(int (*edge)[VERTEXNUM], int start, int end, int value){
        edge[start][end] = value;
        edge[end][start] = value;
}
//打印存儲的圖
void displayGraph(int (*edge)[VERTEXNUM]){
        int i,j;
        for(i=0;i<VERTEXNUM;i++){
                for(j=0;j<VERTEXNUM;j++){
                        printf("%d ",edge[i][j]);
                }
                printf("\n");
        }
}
void prim(int (*edge)[VERTEXNUM], int (**tree)[VERTEXNUM], int startVertex, int* vertexStatusArr){
	//申請存儲樹的內(nèi)存
        *tree = (int (*)[VERTEXNUM])malloc(sizeof(int)*VERTEXNUM*VERTEXNUM);
        int i,j;
        for(i=0;i<VERTEXNUM;i++){
                for(j=0;j<VERTEXNUM;j++){
                       (*tree)[i][j] = 0;
                }
        }
	//從頂點0開始，則頂點0就是已訪問的
        vertexStatusArr[0] = 1;
        int least, start, end, vNum = 1;
	//如果還頂點還沒有訪問完
        while(vNum < VERTEXNUM){
                least = 9999;
                for(i=0;i<VERTEXNUM;i++){
			//選擇已經(jīng)訪問過的點
                        if(vertexStatusArr[i] == 1){
                                for(j=0;j<VERTEXNUM;j++){
					//選擇一個沒有訪問過的點
                                        if(vertexStatusArr[j] == 0){
						//選出一條value最小的邊
                                                if(edge[i][j] != 0 && edge[i][j] < least){
                                                        least = edge[i][j];
                                                        start = i;
                                                        end = j;
                                                }
                                        }
                                }
                        }
                }
                vNum++;
		//將點設(shè)置為訪問過
                vertexStatusArr[end] = 1;
		//將邊加到樹中
                createGraph(*tree,start,end,least);
        }
}

結(jié)果

優(yōu)先隊列

普通的隊列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，元素在隊列尾追加，而從隊列頭刪除。

優(yōu)先隊列中，元素被賦予優(yōu)先級。當(dāng)訪問元素時，具有最高優(yōu)先級的元素最先刪除。優(yōu)先隊列具有最高級先出（first in, largest out）的行為特征。

優(yōu)先隊列代碼實現(xiàn)

基本類型優(yōu)先序列

#include <iostream>
#include <queue>
using namespace std;
//方法1
struct tmp1 //運算符重載<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大頂堆
    }
};
//方法2
struct tmp2 //重寫仿函數(shù)
{
    bool operator() (tmp1 a, tmp1 b)
    {
        return a.x < b.x; //大頂堆
    }
};
int main()
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty())
    {
        cout << d.top().x << '\n';
        d.pop();
    }
    cout << endl;
    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(b);
    f.push(c);
    f.push(a);
    while (!f.empty())
    {
        cout << f.top().x << '\n';
        f.pop();
    }
}

自定義類型優(yōu)先序列

#include <iostream>
#include <queue>
using namespace std;
//方法1
struct tmp1 //運算符重載<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大頂堆
    }
};
//方法2
struct tmp2 //重寫仿函數(shù)
{
    bool operator() (tmp1 a, tmp1 b)
    {
        return a.x < b.x; //大頂堆
    }
};
int main()
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty())
    {
        cout << d.top().x << '\n';
        d.pop();
    }
    cout << endl;
    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(b);
    f.push(c);
    f.push(a);
    while (!f.empty())
    {
        cout << f.top().x << '\n';
        f.pop();
    }
}

結(jié)果