数据结构__最小生成树（prim算法）

返回最小生成树的边权值之和。

prim算法核心思想就是贪心，与dijstra算法结构如出一辙。

代码和注释如下：

#include<iostream>
#include<vector>
#include<iomanip>//用于格式化输出
#define maxn 1000//最大节点数
#define inf 1000000000//模拟距离无限大
int G[maxn][maxn];//邻接阵，用于比较时提取G[u][v]
using namespace std;

struct node
{
	int adjvex;//节点序号
	char data;//节点英文字母
	int weight;//权重
};

vector<node> adj[maxn];//定义邻接表
int n;//定点数

//邻接表节点创建
void createNode(char a,int i,int w=0)
{
	node temp;
	temp.adjvex = a-'a';
	temp.data = a;
	temp.weight = w;
	adj[i].push_back(temp);
}

//邻接表键入
void create()
{
	int m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		char tempA;
		cin >> tempA;
		createNode(tempA, i);
	}
	char a, b;
	int cost,aa,bb;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> cost;
		for (int j = 0; j < n; j++)
		{
			if (a == adj[j][0].data)
				aa = adj[j][0].adjvex;
			if (b == adj[j][0].data)
				bb = adj[j][0].adjvex;
		}
		G[aa][bb] =G[bb][aa]= cost;
		createNode(b, aa, cost);
	}
}

//打印邻接表
void print()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < adj[i].size(); j++)
		{
			cout << adj[i][j].data <<adj[i][j].weight << ' ';
		}
		cout << endl;
	}
}

int d[maxn];//起点到达各点的最短路径长度
bool vis[maxn] = { false };//标记数组是否被访问

int prim()//与dijkstra算法结构类似
{
	fill(d, d + maxn, inf);//初始化d数组全为inf
	d[0] = 0;//只有0号顶点到集合s的距离为0，其余都为inf
	int ans = 0;//存放最小生成树的边权之和
	for (int i = 0; i < n; i++)//循环n趟
	{
		int u = -1, min = inf;//u使d[u]最小min存放最小的d[u]
		for (int j = 0; j < n; j++)
		{
			if (vis[j] == false && d[j] < min)
			{
				u = j;
				min = d[j];
			}
		}
		if (u == -1)return -1;//找不到与s相同的节点了，结束该函数
		vis[u] = true;//标记u为已访问
		ans += d[u];//将与集合s距离最小的边加入最小生成树
		for (int j=0;j<adj[u].size();j++)
		{
			int v = adj[u][j].adjvex;//通过邻接表获得u能访问的节点v
			if (vis[v] == false && adj[u][j].weight < d[v])
				d[v] =G[u][v];//贪心，使得更优化
		}
	}
	return ans;
}

int main(void)
{
	fill(G[0], G[0] + maxn * maxn, inf);
	create();
	cout << endl;
	for (int i = 0; i < 6; i++)
	{
		for (int j = 0; j < 6; j++)
		{
			cout << setw(10)<<right << G[i][j] << "           ";
		}
		cout << endl;
	}
	cout << endl;
	cout << prim() << endl;
	system("pause");
	return 0;
}