Prim

Prim算法是一种用于计算加权无向连通图的最小生成树的经典算法。以下是该算法的C++实现：

void Prim(vector<vector<int>> & A, int v) {
	int n = A.size();           // 表示图中顶点的数量
	vector<int> U(n, 0);        // U[i]=1表示顶点i已加入最小生成树
	vector<int> closest(n);     // closest[i]表示与顶点i最近的树中顶点
	vector<int> lowcost(n, INT_MAX);  // lowcost[i]表示顶点i与树中顶点的最小权重
	int mincost;
	// 初始化：将v作为起始顶点，更新其他点到v的距离
	for (int i = 0; i < n; i++) {
		closest[i] = v;
		lowcost[i] = A[v][i];
	}
	U[v] = 1;  // 将起始顶点加入树中
	// 循环n-1次，每次添加一个新顶点到最小生成树
	for (int i = 1; i < n; i++) {
		mincost = INT_MAX;
		int u = -1;
		// 在所有未加入树的顶点中找到距离树最近的顶点
		for (int j = 0; j < n; j++) {
			if (U[j] == 0 && lowcost[j] < mincost) {
				mincost = lowcost[j];
				u = j;
			}
		}
		// 检查图的连通性
		if (u == -1 || mincost == INT_MAX) {
			cout << "图不连通！" << endl;
			return;
		}	
		cout << "选择边 (" << closest[u] << ", " << u << ") 权重: " << mincost << endl;
		U[u] = 1;  // 将顶点u加入树中
		// 更新其他未加入树的顶点到树的距离
		for (int j = 0; j < n; j++) {
			if (U[j] == 0 && A[u][j] < lowcost[j]) {
				lowcost[j] = A[u][j];
				closest[j] = u;
			}
		}
	}
}