Prim算法、优先队列【贪心算法】_prim算法 优先队列

Prim算法、优先队列【贪心算法】

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

Prim算法

基于最小生成树的该性质，使用prim算法来求解最小生成树。
贪心算法属性：一个局部全优解，也是全局全优解
思想：设T是最小生成树，A<=V,(u,v)是连接着A到A补集（一个在A中，一个不在A中）最小权值的边，则一定是最小生成树边。

prim代码实现【C++】

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
'
运行
运行

结果

优先队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。
优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。

优先队列代码实现【C++】

基本类型优先序列

#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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

自定义类型优先序列

#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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

结果