数据结构：最小生成树--Prim算法

àì夳堔傛蜴生んèń 2022-06-12 04:24 161阅读 0赞

最小生成树：Prim算法

### 最小生成树 ###

给定一无向带权图，顶点数是n，要使图连通只需n-1条边，若这n-1条边的权值和最小，则称有这n个顶点和n-1条边构成了图的最小生成树(minimum-cost spanning tree)。

### Prim算法 ###

Prim算法是解决最小生成树的常用算法。它采取贪心策略，从指定的顶点开始寻找最小权值的邻接点。图G=<V,E>，初始时S=\{V0\}，把与V0相邻接，且边的权值最小的顶点加入到S。不断地把S中的顶点与V-S中顶点的最小权值边加入，直到所有顶点都已加入到S中。

### 算法说明 ###

为了方便寻找最小权值的边，构建一**最近边**结构体CloseEdge：

**\[cpp\]**  view plain  copy

print ?

1.  //最近边
2.  typedef struct closeedge\_tag
3.  \{
4.  int adjvex; //邻接点
5.  int weight; //权值
6.  \}CloseEdge;

//最近边
    typedef struct closeedge_tag
    {
    	int adjvex; //邻接点
    	int weight; //权值
    }CloseEdge;

创建一数组CloseEdge closeedge\[n\];顶点u属于S，顶点v属于V-S，则closeedge\[v\].weight=min\{weight(u,v)\};closeedge\[v\].adjvex=u;另外设置一bool型的数组add，标记顶点i是否已加入S。结合closeedge和add即可得到当前最小权值边。每当有新的节点加入S时，则需更新closeedge。具体细节看代码。

### 实例 ###

![20140804235619510][]

从V0开始

![20140805002459834][]

### 代码 ###

类定义

**\[cpp\]**  view plain  copy

print ?

1.  \#include<iostream> 
2.  \#include<iomanip>
3.  \#include<stack>
4.  using namespace std;
5.  \#define MAXWEIGHT 100
6.  //边
7.  typedef struct edge\_tag
8.  \{
9.  int tail;
10. int head;
11. \}Edge;
12. //最近边
13. typedef struct closeedge\_tag
14. \{
15. int adjvex; //邻接点
16. int weight; //权值
17. \}CloseEdge;
18. class Graph
19. \{
20. private:
21. //顶点数 
22. int numV;
23. //边数 
24. int numE;
25. //邻接矩阵 
26. int \*\*matrix;
27. public:
28. Graph(int numV);
29. //建图 
30. void createGraph(int numE);
31. //析构方法 
32. ~Graph();
33. //Prim算法
34. void Prim(int);
35. int minEdgeVex(CloseEdge\*, bool\*);
36. void updateCloseEdge(CloseEdge\*, bool\*, int);
37. //打印邻接矩阵 
38. void printAdjacentMatrix();
39. //检查输入 
40. bool check(int, int, int);
41. \};

#include<iostream>  
    #include<iomanip>
    #include<stack>
    using namespace std;
    #define MAXWEIGHT 100
    //边
    typedef struct edge_tag
    {
    	int tail;
    	int head;
    }Edge;
    //最近边
    typedef struct closeedge_tag
    {
    	int adjvex; //邻接点
    	int weight; //权值
    }CloseEdge;
    class Graph
    {
    private:
    	//顶点数  
    	int numV;
    	//边数  
    	int numE;
    	//邻接矩阵  
    	int **matrix;
    public:
    	Graph(int numV);
    	//建图  
    	void createGraph(int numE);
    	//析构方法  
    	~Graph();
    	//Prim算法
    	void Prim(int);
    	int minEdgeVex(CloseEdge*, bool*);
    	void updateCloseEdge(CloseEdge*, bool*, int);
    	//打印邻接矩阵  
    	void printAdjacentMatrix();
    	//检查输入  
    	bool check(int, int, int);
    };

类实现

**\[cpp\]**  view plain  copy

print ?

1.  //构造函数，指定顶点数目
2.  Graph::Graph(int numV)
3.  \{
4.  //对输入的顶点数进行检测
5.  while (numV <= 0)
6.  \{
7.  cout << "顶点数有误！重新输入 ";
8.  cin >> numV;
9.  \}
10. this\->numV = numV;
11. //构建邻接矩阵，并初始化
12. matrix = new int\*\[numV\];
13. int i, j;
14. for (i = 0; i < numV; i++)
15. matrix\[i\] = new int\[numV\];
16. for (i = 0; i < numV; i++)
17. for (j = 0; j < numV; j++)
18. \{
19. if (i == j)
20. matrix\[i\]\[i\] = 0;
21. else
22. matrix\[i\]\[j\] = MAXWEIGHT;
23. \}
24. \}
25. void Graph::createGraph(int numE)
26. \{
27. /\*
28.  对输入的边数做检测
29.  一个numV个顶点的有向图，最多有numV\*(numV - 1)条边
30.  \*/
31. while (numE < 0 || numE > numV\*(numV - 1))
32. \{
33. cout << "边数有问题！重新输入 ";
34. cin >> numE;
35. \}
36. this\->numE = numE;
37. int tail, head, weight, i;
38. i = 0;
39. cout << "输入每条边的起点(弧尾)、终点(弧头)和权值" << endl;
40. while (i < numE)
41. \{
42. cin >> tail >> head >> weight;
43. while (!check(tail, head, weight))
44. \{
45. cout << "输入的边不正确！请重新输入 " << endl;
46. cin >> tail >> head >> weight;
47. \}
48. //Prim算法主要针对的是无向图
49. matrix\[tail\]\[head\] = weight;
50. matrix\[head\]\[tail\] = weight;
51. i++;
52. \}
53. \}
54. Graph::~Graph()
55. \{
56. int i;
57. for (i = 0; i < numV; i++)
58. delete\[\] matrix\[i\];
59. delete\[\]matrix;
60. \}
61. /\*
62. Prim算法
63. 求最小生成树
64. \*/
65. void Graph::Prim(int vertex)
66. \{
67. //有numV个顶点的图的最小生成树有numV-1条边
68. Edge \*edges = new Edge\[numV - 1\];
69. //标记顶点是否加入
70. bool \*add = new bool\[numV\];
71. memset(add, 0, numV);
72. //先把vertex加入
73. add\[vertex\] = true;
74. //最近边
75. CloseEdge \*closeedge = new CloseEdge\[numV\];
76. int i;
77. //初始化最近边
78. for (i = 0; i < numV; i++)
79. \{
80. closeedge\[i\].weight = matrix\[vertex\]\[i\];
81. if (!add\[i\] && matrix\[vertex\]\[i\] > 0 && matrix\[vertex\]\[i\] < MAXWEIGHT)
82. closeedge\[i\].adjvex = vertex;
83. \}
84. int v, count = 0;
85. while (count < numV - 1)
86. \{
87. //获取最近边的邻接点
88. v = minEdgeVex(closeedge, add);
89. add\[v\] = true;
90. //把最小权值边依次加入数组edges
91. edges\[count\].tail = closeedge\[v\].adjvex;
92. edges\[count\].head = v;
93. //更新最近边
94. updateCloseEdge(closeedge, add, v);
95. count++;
96. \}
97. cout << "从顶点 " << vertex << " 开始，最小生成树的边是" << endl;
98. for (i = 0; i < count; i++)
99. cout << edges\[i\].tail << "---" << edges\[i\].head << endl;
100. //释放空间
101. delete\[\]edges;
102. delete\[\]add;
103. delete\[\]closeedge;
104. \}
105. //从closeedge中寻找最小边的邻接顶点
106. int Graph::minEdgeVex(CloseEdge \*closeedge, bool \*add)
107. \{
108. int i, v, w;
109. v = 0;
110. w = MAXWEIGHT;
111. for (i = 0; i < numV ; i++)
112. if (!add\[i\] && closeedge\[i\].weight < w)
113. \{
114. w = closeedge\[i\].weight;
115. v = i;
116. \}
117. return v;
118. \}
119. //顶点v的加入后，需要更新最近边
120. void Graph::updateCloseEdge(CloseEdge\* closeedge, bool \*add, int v)
121. \{
122. int i;
123. for (i = 0; i < numV; i++)
124. if (!add\[i\] && matrix\[v\]\[i\] < closeedge\[i\].weight)
125. \{
126. closeedge\[i\].adjvex = v;
127. closeedge\[i\].weight = matrix\[v\]\[i\];
128. \}
129. \}
130. //打印邻接矩阵 
131. void Graph::printAdjacentMatrix()
132. \{
133. int i, j;
134. cout.setf(ios::left);
135. cout << setw(7) << " ";
136. for (i = 0; i < numV; i++)
137. cout << setw(7) << i;
138. cout << endl;
139. for (i = 0; i < numV; i++)
140. \{
141. cout << setw(7) << i;
142. for (j = 0; j < numV; j++)
143. cout << setw(7) << matrix\[i\]\[j\];
144. cout << endl;
145. \}
146. \}
147. bool Graph::check(int tail, int head, int weight)
148. \{
149. if ((tail == head) || tail < 0 || tail >= numV
150. || head < 0 || head >= numV
151. || weight <= 0 || weight >= MAXWEIGHT)
152. return false;
153. return true;
154. \}

//构造函数，指定顶点数目
    Graph::Graph(int numV)
    {
    	//对输入的顶点数进行检测
    	while (numV <= 0)
    	{
    		cout << "顶点数有误！重新输入 ";
    		cin >> numV;
    	}
    	this->numV = numV;
    	//构建邻接矩阵，并初始化
    	matrix = new int*[numV];
    	int i, j;
    	for (i = 0; i < numV; i++)
    		matrix[i] = new int[numV];
    	for (i = 0; i < numV; i++)
    	for (j = 0; j < numV; j++)
    	{
    		if (i == j)
    			matrix[i][i] = 0;
    		else
    			matrix[i][j] = MAXWEIGHT;
    	}
    }
    void Graph::createGraph(int numE)
    {
    	/*
    	对输入的边数做检测
    	一个numV个顶点的有向图，最多有numV*(numV - 1)条边
    	*/
    	while (numE < 0 || numE > numV*(numV - 1))
    	{
    		cout << "边数有问题！重新输入 ";
    		cin >> numE;
    	}
    	this->numE = numE;
    	int tail, head, weight, i;
    	i = 0;
    	cout << "输入每条边的起点(弧尾)、终点(弧头)和权值" << endl;
    	while (i < numE)
    	{
    		cin >> tail >> head >> weight;
    		while (!check(tail, head, weight))
    		{
    			cout << "输入的边不正确！请重新输入 " << endl;
    			cin >> tail >> head >> weight;
    		}
    		//Prim算法主要针对的是无向图
    		matrix[tail][head] = weight;
    		matrix[head][tail] = weight;
    		i++;
    	}
    }
    Graph::~Graph()
    {
    	int i;
    	for (i = 0; i < numV; i++)
    		delete[] matrix[i];
    	delete[]matrix;
    }
    /*
    Prim算法
    求最小生成树
    */
    void Graph::Prim(int vertex)
    {
    	//有numV个顶点的图的最小生成树有numV-1条边
    	Edge *edges = new Edge[numV - 1];
    	//标记顶点是否加入
    	bool *add = new bool[numV];
    	memset(add, 0, numV);
    	//先把vertex加入
    	add[vertex] = true;
    	//最近边
    	CloseEdge *closeedge = new CloseEdge[numV];
    	int i;
    	//初始化最近边
    	for (i = 0; i < numV; i++)
    	{
    		closeedge[i].weight = matrix[vertex][i];
    		if (!add[i] && matrix[vertex][i] > 0 && matrix[vertex][i] < MAXWEIGHT)
    			closeedge[i].adjvex = vertex;
    	}
    	int v, count = 0;
    	while (count < numV - 1)
    	{
    		//获取最近边的邻接点
    		v = minEdgeVex(closeedge, add);
    		add[v] = true;
    		//把最小权值边依次加入数组edges
    		edges[count].tail = closeedge[v].adjvex;
    		edges[count].head = v;
    		//更新最近边
    		updateCloseEdge(closeedge, add, v);
    		count++;
    	}
    	cout << "从顶点 " << vertex << " 开始，最小生成树的边是" << endl;
    	for (i = 0; i < count; i++)
    		cout << edges[i].tail << "---" << edges[i].head << endl;
    	//释放空间
    	delete[]edges;
    	delete[]add;
    	delete[]closeedge;
    }
    //从closeedge中寻找最小边的邻接顶点
    int Graph::minEdgeVex(CloseEdge *closeedge, bool *add)
    {
    	int i, v, w; 
    	v = 0;
    	w = MAXWEIGHT;
    	for (i = 0; i < numV ; i++)
    	if (!add[i] && closeedge[i].weight < w)
    	{
    		w = closeedge[i].weight;
    		v = i;
    	}
    	return v;
    }
    //顶点v的加入后，需要更新最近边
    void Graph::updateCloseEdge(CloseEdge* closeedge, bool *add, int v)
    {
    	int i;
    	for (i = 0; i < numV; i++)
    	if (!add[i] && matrix[v][i] < closeedge[i].weight)
    	{
    		closeedge[i].adjvex = v;
    		closeedge[i].weight = matrix[v][i];
    	}
    }
    //打印邻接矩阵  
    void Graph::printAdjacentMatrix()
    {
    	int i, j;
    	cout.setf(ios::left);
    	cout << setw(7) << " ";
    	for (i = 0; i < numV; i++)
    		cout << setw(7) << i;
    	cout << endl;
    	for (i = 0; i < numV; i++)
    	{
    		cout << setw(7) << i;
    		for (j = 0; j < numV; j++)
    			cout << setw(7) << matrix[i][j];
    		cout << endl;
    	}
    }
    bool Graph::check(int tail, int head, int weight)
    {
    	if ((tail == head) || tail < 0 || tail >= numV 
    		|| head < 0 || head >= numV
    		|| weight <= 0 || weight >= MAXWEIGHT)
    		return false;
    	return true;
    }

主函数

**\[cpp\]**  view plain  copy

print ?

1.  int main()
2.  \{
3.  cout << "\*\*\*\*\*\*Prim\*\*\*by David\*\*\*" << endl;
4.  int numV, numE;
5.  cout << "建图..." << endl;
6.  cout << "输入顶点数 ";
7.  cin >> numV;
8.  Graph graph(numV);
9.  cout << "输入边数 ";
10. cin >> numE;
11. graph.createGraph(numE);
12. cout << endl << "Prim..." << endl;
13. /\*
14.  由于输出结果太长，不利于截图，故只打印一半的节点
15.  要想获得从所有节点开始的最小生成树，修改i的变化范围即可
16.  \*/
17. for (int i = 0; i < numV / 2; i++)
18. graph.Prim(i);
19. system("pause");
20. return 0;
21. \}

int main()
    {
    	cout << "******Prim***by David***" << endl;
    	int numV, numE;
    	cout << "建图..." << endl;
    	cout << "输入顶点数 ";
    	cin >> numV;
    	Graph graph(numV);
    	cout << "输入边数 ";
    	cin >> numE;
    	graph.createGraph(numE);
    	cout << endl << "Prim..." << endl;
    	/*
    	由于输出结果太长，不利于截图，故只打印一半的节点
    	要想获得从所有节点开始的最小生成树，修改i的变化范围即可
    	*/
    	for (int i = 0; i < numV / 2; i++)
    		graph.Prim(i);
    	system("pause");
    	return 0;
    }

运行

![20140804235619510][] ![20140805102341924][]

完整代码下载：[Prim算法][Prim]

转载请注明出处，本文地址：[http://blog.csdn.net/zhangxiangdavaid/article/details/38377091][http_blog.csdn.net_zhangxiangdavaid_article_details_38377091]

若有所帮助，顶一个哦！

专栏目录：

*  [数据结构与算法目录 ][Link 1]
 *  [c指针][c]

[20140804235619510]: /images/20220612/91b34ed7fabb4d4abe3ec820c729e0ca.png
[20140805002459834]: /images/20220612/798a590fc9bd487180998ff6c615f521.png
[20140805102341924]: /images/20220612/f14e3e30031c4361b0d81a258aabcdd1.png
[Prim]: http://download.csdn.net/detail/zhangxiangdavaid/7715647
[http_blog.csdn.net_zhangxiangdavaid_article_details_38377091]: http://blog.csdn.net/zhangxiangdavaid/article/details/38377091
[Link 1]: http://blog.csdn.net/zhangxiangdavaid/article/details/25082013
[c]: http://blog.csdn.net/zhangxiangdavaid/article/details/37885275#t1