最小生成树之普利姆（ Prim ）算法

如果想看克鲁斯卡尔算法（Kruskal），请移步

--------->这是链接🔗{{>_<}}<-----------

- 例子
- 图示
- 代码

我们来讲述普利姆（ Prim ）算法。

和克鲁斯卡尔算法一样，普利姆算法也是一种构造最小生成树的算法。

主要思想是：
首先随意从一个点出发，然后每次找他们的最小相邻边，每经过一个顶点，那边找其顶点的最小权值的边。一直到找到了 n 条边，( n=定点数-1 ) 然后我们的算法结束

普利姆算法是利用了贪心思想的特性，但是对于有负权值的边，普利姆算法并不适用，此时应该用克鲁斯卡尔算法 （ ------>这是我的另一篇文章，讲述克鲁斯卡尔算法,有兴趣看看啊♪(´▽｀)<------ ）

举个栗子 (╹ڡ╹ ) ：比如有六个城市，分别是城市1，城市2，城市3，城市4，城市5，城市6，我们的目标是：选择几条线路，把这几个城市连起来，让城市间能够相互到达，但是不能有回路。如图.....

在这几个城市中，我们测量了每个城市之间的路线，他们的权值分别如下:

开始城市

到达城市

路线长度(权值)

城市1

城市2

城市1

城市3

城市1

城市4

城市1

城市5

城市2

城市6

城市2

城市4

城市6

城市5

城市4

城市3

也就是如图所示：

然后，我们的目标是，从这几条边中找到能够连通所有点的边并且这些边是最小权值的。也就是像下面的图一样

然后我们，从城市1开始吧 o( * ￣ ▽ ￣ * )o。

从城市1开始的话，我们会把城市1所相邻的边放进一个集合里面，然后找城市1相邻的边的最小值。我们很容易可以找到，它是1，那么我们把1选上，然后1所相连的是城市2，这样，我们找到了第一条路径，并且这条路径是能够从城市1到达城市2的 (o゜▽゜)o☆

从城市1开始，我们把边1，2，5，12放进集合了，然后我们选了1，现在把1从集合里面移除。由于加入了城市2，那么我们把城市2相关邻的边放进集合里面，此时集合里面就有了2，5，12，4，12，然后我们再在这里面找权值最小的边，然后再相连，然后重复这个操作。

当你找到一条边，这条边刚刚好两边都经历过了，那我们就舍弃这条边，然后继续向下找，直到所有的点都遍历过了之后，就结束操作，我们就构成了一棵最小生成树。

work1

work2

work3

work4

<h2 id="3"></h2> - \[返回\](#back)

然后让我们来看看代码的实现。代码实现，我采用了邻接矩阵的存储结构

main.cpp

1#include"GraphPrim.h"
2
3int main()
4{
5	GraphPrim g1;
6	g1.Init();
7	g1.Display();
8	return 0;
9}
10

GraphPrim.h

1#pragma once
2#ifndef _GRAPHPRIM_H_
3#define _GRAPHPRIM_H_
4#include<iostream>
5#include<cstdlib>
6#include<vector>
7using namespace std;
8
9const int MAX = INT_MAX;
10
11class GraphPrim
12{
13private:
14	vector<vector<int>>graph;//邻接矩阵存储点与边的关系
15	vector<bool>visited;//判断是否经历过
16	vector<int>side;
17
18	vector<int>node;//取点的路径，用来存放输出点的顺序
19	vector<int>useSide;//使用的边，用来存放边的权值
20
21	int nodeNumber;//点的个数
22	int startPoint;//开始点
23	int sum;
24
25	int findMin(vector<int>& ans);//返回下标
26
27public:
28	void Init();//初始化
29	void Prim(int start);//普利姆算法，以及开始点
30	void Display();//显示参数
31};
32
33
34#endif // !_GRAPHPRIM_H_
35
36

Graphprim.cpp

1#include "GraphPrim.h"
2
3int GraphPrim::findMin(vector<int>& ans)
4{
5	int index = 0;
6	int min = ans[0];
7	for (int i = 0; i < ans.size(); i++)
8	{
9		if (min > ans[i])
10		{
11			min = ans[i];
12			index = i;
13		}
14	}
15	return index;
16}
17
18void GraphPrim::Init()
19{
20	cout << "请输入点的个数" << endl;
21	cin >> nodeNumber;
22
23	visited.resize(nodeNumber + 1);//初始化
24
25	graph.resize(nodeNumber + 1);//初始化
26	for (int i = 0; i <nodeNumber + 1; i++)
27		graph[i].resize(nodeNumber + 1, MAX);
28
29	cout << "请输入开始点" << endl;
30	cin >> startPoint;
31	int a, b;
32	cout << "请输入出发点、到达点和路径长度,以‘#’为全部结束" << endl;
33	while ((cin >> a && a != '#') && (cin >> b && b != '#'))
34	{
35		cin >> graph[a][b];//输入权值
36		graph[b][a] = graph[a][b];
37	}
38}
39
40void GraphPrim::Prim(int start)
41{
42	int temp;
43	sum = 0;		
44	side.resize(nodeNumber + 1);
45	node.push_back(start);
46	visited[start] = true;
47	for(int i = 1; i <= nodeNumber; i++)
48		side[i] = graph[start][i];	
49	for(int i = 1; i <= nodeNumber; i++)//找生成树集合点集相连最小权值的边	
50	{
51		temp = MAX;
52		for(int j = 1; j <= nodeNumber; j++)
53			if (!visited[j] && temp > side[j])
54			{
55				temp = side[start = j];
56			}
57		if(temp == MAX)//如果是无穷了
58			break;	
59		visited[start] = true; //加入最小生成树集合
60		node.push_back(start);
61		useSide.push_back(temp);
62		sum += temp;//记录权值之和		
63		for(int j = 1; j <= nodeNumber; ++j) //更新边数组	
64			if (!visited[j] && side[j] > graph[start][j])
65			{
66				side[j] = graph[start][j];
67			}
68	}
69}
70
71void GraphPrim::Display()
72{
73	Prim(startPoint);
74	cout << "显示最大权值" << sum << endl;
75	cout << "路径显示: ";
76	for (int i = 0; i < node.size(); i++)
77		cout << node[i] << " ";
78	cout << endl;
79}
80
81

Prim 普利姆算法