最小生成树（Prim算法）

#if 0
#include<iostream>
using namespace std;
#define maxint 999

template<class Type>
void Prim(int n, Type ** c) {//c[i][j]表示边(i,j)的权值，n是顶点个数
Type *lowcost=new Type[n+1];
int *closest=new int[n+1];//closest[i]表示点i在S中的邻接顶点
bool *s=new bool[n+1];
s[1] = true;//第一个顶点在S集合中
//选取第一个顶点
for (auto i = 2; i <= n; i++) {
lowcost[i] = c[1][i];//从2开始的顶点与顶点1的构成的边的权值
closest[i] = 1;//从2开始的每个顶点先默认与第一个顶点邻接
s[i] = false;
}
for (auto i = 1; i < n; i++) {
Type min = maxint;
int j = 1;
//从V-S集合中找到接下来的第一个顶点
for (auto k = 2; k <= n; k++)
if ((lowcost[k] < min) && (!s[k])) {
min = lowcost[k];
j = k;
}
cout << j << " " << closest[j] << ‘\n‘;
s[j] = true;//向S 集合中添加顶点j
for (auto k = 2; k <= n; k++)
if ((c[j][k] < lowcost[k]) && (!s[k])) {
lowcost[k] = c[j][k];
closest[k] = j;
}
}
}
int main()
{
int n = 0;
n = 7;
int** c = new int*[7];
for (auto i = 0; i < 7; i++)
c[i] = new int[7];
for (auto i = 0; i < n; i++)
for (auto j = 0; j < n; j++)
cin >> c[i][j];
Prim(n-1, c);

}

/*

0 0 0 0 0 0 0
0 0 6 1 5 999 999
0 6 0 5 999 3 999
0 1 5 0 5 6 4
0 5 999 5 0 999 2
0 999 3 6 999 0 6
0 999 999 4 2 6 0

*/
#endif

#if 0
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int MaxSize = 100;
const int MAX = 9999;

class MGraph
{
string vertex[MaxSize]; //图的顶点信息
int adj[MaxSize][MaxSize]; //图的邻接矩阵
int vertexNum, edgeNum;//顶点个数，边的个数
public:
MGraph(int n);//初始化
int W(int i, int j);
void InsertEdge(int i, int j, int p);
int VexNum()
{
return vertexNum;
}
friend void Prim(MGraph& g, int u0);
};

MGraph::MGraph(int n)
{
vertexNum = n;
edgeNum = 0;
memset(adj, 0, sizeof(adj)); //将邻接矩阵所有元素赋为0
}

void MGraph::InsertEdge(int i, int j, int p) //插入顶点i、j依附的边以及该边的权值
{
adj[i][j] = adj[j][i] = p;
edgeNum++;
}

int MGraph::W(int i, int j)
{
return adj[i][j];
}

void Prim(MGraph& g, int u0)
{
int k;
int n = g.VexNum();
struct node
{
int adjvex;
int lowcost;
}closedge[MaxSize];
closedge[u0].adjvex = u0;
closedge[u0].lowcost = 0;
for (int v = 0; v < n; v++)
{
if (v != u0)
{
closedge[v].adjvex = u0;
closedge[v].lowcost = g.W(u0, v);
}
}
closedge[u0].lowcost = 0;
for (int i = 0; i <= n - 2; i++)
{
k = 0;
int minw = MAX;
for (int v = 0; v <= n - 1; v++)
{
if (closedge[v].lowcost > 0 && closedge[v].lowcost < minw)
{
k = v;
minw = closedge[v].lowcost;
}
}
cout << "(" << closedge[k].adjvex << "," << k << ")" << ":" << minw << " " << endl;
closedge[k].lowcost = 0; //顶点k并入U集
for (int v = 0; v <= n - 1; v++)
{
if (closedge[v].lowcost != 0 && g.W(k, v) < closedge[v].lowcost)
{
closedge[v].lowcost = g.W(k, v);
closedge[v].adjvex = k;
}
}
}
}

int main()
{
struct Edge
{
int from, end, power;
};

int n = 6; //6个顶点
int e = 10;
Edge b[] = { {0,1,6},{0,2,1},{0,3,5},{1,2,5},{1,4,3},{2,3,5},{2,4,6},{2,5,4},{3,5,2},{4,5,6} };
MGraph m(n);
for (int k = 0; k < e; k++)m.InsertEdge(b[k].from, b[k].end, b[k].power); //插入所有边,将邻接矩阵赋值
Prim(m, 0);
return 0;
}

#endif

最小生成树（Prim算法）

原文：https://www.cnblogs.com/msboke/p/14746049.html