亲宝软件园·资讯

展开

C++ Prim算法与优先队列

成就一亿技术人 人气:0

贪心算法的本质是:一个问题的局部最优解,也是该问题的全局最优解。

最小生成树的最优子结构性质:假设一个无向图包含两部分A,B,其中A为最小生成树部分,B为剩余部分,则存在以下性质:该无向图中一个顶点在A部分,另一个顶点在B部分的边中,权值最小的边一定属于整个无向图的最小生成树,即部分最小权值是整个最小生成树的局部最有解,该性质符合贪心算法的特点。

Prim算法

基于最小生成树的该性质,使用prim算法来求解最小生成树。

贪心算法属性:一个局部全优解,也是全局全优解

思想:设T是最小生成树,A<=V,(u,v)是连接着A到A补集(一个在A中,一个不在A中)最小权值的边,则一定是最小生成树边。

prim代码实现

#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){
	//动态创建存放边的二维数组  
        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;
                }
        }
	//存放顶点的遍历状态,0:未遍历,1:已遍历 
        int* vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM);
        for(i=0;i<VERTEXNUM;i++){
                vertexStatusArr[i] = 0;
        }
        printf("after init:\n");
        displayGraph(edge);
	//创建图  
        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;
}
//创建图
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){
	//申请存储树的内存
        *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++){
			//选择已经访问过的点
                        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++;
		//将点设置为访问过
                vertexStatusArr[end] = 1;
		//将边加到树中
                createGraph(*tree,start,end,least);
        }
}

结果

优先队列

普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。

优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。

优先队列代码实现

基本类型优先序列

#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 //重写仿函数
{
    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();
    }
}

自定义类型优先序列

#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 //重写仿函数
{
    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();
    }
}

结果

加载全部内容

相关教程
猜你喜欢
用户评论