Prim算法（C++）

#include<iostream>
#include<algorithm>
using namespace std;
int graph[10][10];
void createGraph(int n)
{
	int gLeft,gRight,weight;
	for(int i=0;i<n;i++){
		cin>>gLeft>>gRight>>weight;
		graph[gLeft][gRight]=weight;
	}
}
void prim(int n)
{
	int adjx[n];//标记节点相连
	int lowcost[n];//最小的路径
	adjx[0]=0;
	lowcost[0]=0;
	for(int i=0;i<n;i++){
		lowcost[i]=graph[0][i];
		adjx[i]=0;
	}
	for(int i=1;i<n;i++){
		int minCost=1000000;
		int h=0;
		for(int j=1;j<n;j++){
			if(lowcost[j]<minCost&&lowcost[j]!=0){
				minCost=graph[0][i];
				h=j;
			}
		}
		if(h){
			cout<<"(V"<<adjx[h]<<"->V"<<h<<") ";
		}
		lowcost[h]=0;
		for(int j=1;j<n;j++){
			if(lowcost[j]>graph[h][j]&&lowcost[j]!=0){//将后面加上的节点指向的最小值输入lowcost
				lowcost[j]=graph[h][j];
				adjx[j]=h;//后面的节点和加上的节点相连
			}
		}
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			graph[i][j]=0;
		}
	}
	int m;
	cin>>m;
	createGraph(m);
	prim(n);
}

这段代码实现了Prim算法,用于求解无向图的最小生成树。以下是对代码的解释:

1. 包含了必要的头文件:`iostream`用于输入输出,`algorithm`用于提供一些算法函数。
2. 定义了一个二维数组`graph`用于存储图的邻接矩阵表示。
3. `createGraph`函数用于创建图,输入格式为每行三个整数,分别表示行、列和边的权重。
4. `prim`函数实现了Prim算法:
   - 初始化两个数组`adjx`和`lowcost`,其中`adjx`用于记录每个节点的前驱节点,`lowcost`用于记录每个节点到最小生成树的最小权重。
   - 首先将起始节点0的`adjx`和`lowcost`初始化为0。
   - 然后遍历其他节点,找到未加入最小生成树的节点中权重最小的节点,并将其加入最小生成树,同时更新其他节点的`lowcost`和`adjx`。
   - 输出最小生成树的边。
5. `main`函数中:
   - 首先输入图的节点数`n`。
   - 初始化`graph`数组。
   - 输入边的数量`m`,并调用`createGraph`函数创建图。
   - 最后调用`prim`函数求解最小生成树。

这个代码实现了Prim算法,用于求解无向图的最小生成树问题。如果需要处理有向图或者其他图算法,可以在此基础上进行扩展和修改。