[C++知识库]prim算法机试模板|C++

prim算法和前面我发的kruskal算法都是求最小生成树的算法，kruskal我总结是暴力解法，prim的话就没有kruskal那么简单暴力，prim是靠着把结点分成两个集合，一个是已经加进来的结点集合，一个是未进来的结点集合，然后依次遍历。

要理解两层循环的意思：
第一层循环：一共要加入N个点，所以循环N次
第二层循环：遍历N个结点，查看是不是未加入的结点，并且比较是不是这个距离比较小。

//prim算法：把结点分成两个集合，一个访问过，一个未访问过，然后两次遍历
#include <stdio.h>
#include <iostream>
#pragma warning(disable:4996);
using namespace std;

int N, M;//N个结点，M条边
const int maxn = 5010;
const int INF = 0x3f3f3f3f;
bool visit[maxn];
int Adj[maxn][maxn];
int Dis[maxn];

int prim()
{
	fill(Dis, Dis + maxn, INF);
	int ans = 0;
	//首先初始化
	Dis[1] = 0;
	for (int i = 2; i <= N; i++)
	{
		Dis[i] = Adj[1][i];
	}

	for (int i = 0; i < N; i++)
	{
		int t = -1;
		for (int j = 1; j <= N; j++)
		{
			if (visit[j] == false && (t == -1 || Dis[j] < Dis[t]))
			{
				t = j;
			}
		}
		if (Dis[t] == INF)
		{
			return INF;
		}
		else
		{
			ans += Dis[t];
		}
		visit[t] = true;
		//更新
		for (int k = 1; k <= N; k++)
		{
			if (Adj[t][k] < Dis[k])
			{
				Dis[k] = Adj[t][k];
			}
		}
	}
	return ans;
}

int main()
{
	scanf("%d %d", &N, &M);
	fill(visit, visit + maxn, false);
	fill(Adj[0], Adj[0] + maxn * maxn, INF);
	//m条边 和路径
	for (int i = 0; i < M; i++)
	{
		int node1, node2,w;
		scanf("%d %d %d", &node1, &node2, &w);
		Adj[node1][node2] = Adj[node2][node1] = min(w, Adj[node1][node2]);
	}
	int ans = prim();
	if (ans == INF) {
		printf("orz");
	}
	else {
		printf("%d\n", ans);
	}
	
}