// 贪心算法 最小生成树问题 - Prim算法
#include <iostream>
using namespace std;
#define M 9999 // maxint，inf，大数，无穷
const int N = 6;// 无向连通带权图的 顶点数
void Prim(int n, int c[][N + 1]);
int main()
{
// 无向连通带权图的邻接矩阵，行和列下标从1开始
int c[N + 1][N + 1] = {
{M, M, M, M, M, M, M},
{M, M, 8, 1, 5, M, M},
{M, 8, M, 3, M, 3, M},
{M, 1, 3, M, 5, 6, 4},
{M, 5, M, 5, M, M, 2},
{M, M, 3, 6, M, M, 6},
{M, M, M, 4, 2, 6, M},
};
cout << "无向连通带权图的矩阵为：\n";
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++){
if(c[i][j]==M)
{
cout << "INF" << "\t";
}
else{
cout << c[i][j] << "\t";
}
}
cout << endl;
}
cout << "\nPrim算法最小生成树选边次序：" << endl;
Prim(N, c);
return 0;
}
void Prim(int n, int c[][N + 1])
{
// 顶点j属于V-S，closest[j]是顶点j在S中的 最邻接顶点
int closest[N + 1]; // j的 最邻接顶点
// 顶点j属于V-S，顶点j到closest[j]和S中的其它邻接顶点k相比
// c[j][closest[j]] <= c[j][k]，即最小权值
int lowcost[N + 1]; // 最小权值，c[j][closest[j]]
bool s[N + 1]; // 顶点集合S
s[1] = true; // 初始S={1}
//初始化
for (int i = 2; i <= n; i++)
{
closest[i] = 1;
lowcost[i] = c[1][i];
s[i] = false;
}
for (int i = 1; i < n; i++)
{
int min = M;
int j = 1;
// 找出V-S中使权值最小的顶点j
for (int k = 2; k <= n; k++)
{
if ((lowcost[k] < min) && (!s[k]))
{
min = lowcost[k];
j = k;
}
}
// 找到符合贪心选择方式的边，将顶点j加入到集合S
cout << closest[j] << "--" << j << endl;
s[j] = true;
// 找到一条边后，更新数组closest和lowcost
for (int k = 2; k <= n; k++)
{
if ((c[j][k] < lowcost[k] && (!s[k])))
{
lowcost[k] = c[j][k];
closest[k] = j;
}
}
}
}
