C++用Prim算法實作無向圖最小生成樹

#include <iostream>
using namespace std;
#define INFINE 99999999//假裝自己是無窮大
const int N = 1010;
int graph[N][N];
int vertexnum, arcnum;
//lowcost[i]:表示以i為終點的邊的最小權值,
//當lowcost[i]=0說明以i為終點的邊的最小權值=0,
//也就是表示i點加入了MST

//mst[i]:表示對應lowcost[i]的起點，
//即說明邊<mst[i],i>是MST的一條邊
void Prim(int v, int n) {
	int sum = 0;
	int locatest[N];
	int mst[N];
	for (int i = 1; i <= n; i++) {
		locatest[i] = graph[v][i];
		mst[i] = v;
	}
	mst[v] = 0;
	locatest[v] = 0;
	for (int i = 2; i <= n; i++) {
		int minx = INFINE;
		int minid = 0;
		for (int k = 1; k <= n; k++) {
			if (locatest[k] != 0 && locatest[k] < minx) {
				minx = locatest[k];
				minid = k;
			}
		}
		cout << "V" << mst[minid] << "-" << "V" << minid << " = " << minx << endl;
		locatest[minid] = 0;
		sum += minx;
		for (int i = 1; i <= n; i++) {
			if ( graph[minid][i] < locatest[i]) {
				locatest[i] = graph[minid][i];
				mst[i] = minid;
			}
		}
	}
	cout << sum << endl;
	return;
}


void CreateGraph() {
	cin >> vertexnum >> arcnum;//輸入點的個數，邊的條數

	for (int i = 1; i <= vertexnum; i++)
		for (int j = 1; j <= vertexnum; j++)
			graph[i][j] = INFINE;
	for (int i = 1; i <= arcnum; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		graph[a][b] = w;//無向圖,故兩邊都要指派
		graph[b][a] = w;
	}
}

int main() {
	CreateGraph();
	Prim(1, vertexnum);//以點1為最小生成樹的起點
	return 0;
}
           

最小生成樹Prim算法了解位址:

https://blog.csdn.net/yeruby/article/details/38615045