prim算法

/*PRim算法与Dijkstra算法使用的思想几乎完全相同，只有在数组d[]的含义上有所区别，其中Dijkstra算法的数组d[]含义为起点s到达顶点Vi的最短距离，而prim算法的数组d[]含义为顶点Vi与集合S(已经处理过的点的集合)的最短距离,两者的区别仅在于最短距离是顶点Vi针对"起点s"还是"集合S"。prim(保持树形keep tree，其中有个p可以联想记忆)算法伪代码如下：//G为图，一般设成全局变量；数组d为顶点与集合S的最短距离Prim(G,d[]){	初始化；	for(循环n次)	{		u = 使d[u]最小的还未被访问的顶点标号；		记u已被访问；		for(从u出发能到达的所有顶点v)		{			if(v未被访问&&以u为中介点使得v与集合S的最短距离d[v]更优)			{				将G[u][v]赋值给v与集合S的最短距离d[v]；			}		}	}}再次说明：Dijkstra算法和prim算法实际上是相同的思路，只不过是数组d[]的含义不同罢了*///prim算法实现代码#include<vector>#include<algorithm>using namespace std;const int MAXV = 1000;//最大顶点数const int INF = 1000000000;//设INF为一个很大的数//邻接矩阵版int n, G[MAXV][MAXV];//n为顶点数，MAXV为最大顶点数int d[MAXV];//顶点与集合S的最短距离bool vis[MAXV] = { false };//标记数组，vis[i]==true表示已访问。初值均为falseint prim()//默认0号为初始点，函数返回最小生成树的边权之和{	fill(d, d + MAXV, INF);//fill函数将整个d数组赋为INF(慎用memset)	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];			}		}		//找不到小于INF的d[u],则剩下的顶点和集合S不连通		if (u == -1)return -1;		vis[u] = true;//标记u为已访问		ans += d[u];//将与集合S距离最小的边加入最小生成树		for (int v = 0; v < n; v++)		{			//v未被访问&&u能到达v&&以u为中介点可以使v离集合S更近			if (vis[v] == false && G[u][v] != INF&&G[u][v] < d[v])			{				d[v] = G[u][v];//将G[u][v]赋值给d[v]			}		}	}	return ans;//返回最小生成树的边权之和}//邻接表版struct Node{	int v, dis;//v为边的目标顶点，dis为边权};vector<Node> Adj[MAXV];//图G，Adj[u]存放从顶点u出发可以到达的所有顶点int n;//n为顶点数，图G使用邻接表实现，MAXV为最大顶点数int d[MAXV];//顶点与集合S的最短距离bool vis[MAXV] = { false };//标记数组,vis[i]==true表示已访问。初值均为falseint prim()//默认0号为初始点，函数返回最小生成树的边权之和{	fill(d, d + MAXV, INF);//fill函数将整个d数组赋为INF(慎用memset)	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++)//找到未访问的顶点中d[]最小的		{			if (vis[j] == false && d[j] < MIN)			{				u = j;				MIN = d[j];			}		}		if (u == -1)return -1;		vis[u] - true;//标记u为已访问		ans += d[u];//将与集合S距离最小的边加入最小生成树		//只有下面这个for与邻接矩阵的写法不同		for (int j = 0; j < Adj[u].size(); j++)		{			int v = Adj[u][j].v;//通过邻接表直接获得u能到达的顶点v			if (vis[v] == false && Adj[u][j].dis < d[v])			{				//如果v未被访问&&以u为中介点可以使v离集合S更近				d[v] = Adj[u][j].dis;//将Adj[u][j].dis赋值给d[v]			}		}	}	return ans;//返回最小生成树的边权之和}