最小生成ツリー~Primアルゴリズム

最小生成ツリーの~プリムアルゴリズム
最小生成ツリーとは、接続された図(n個の点があり、(n−1)個より多い)からn−1個の辺を選択してn個の点を相互に接続し、このツリーの総重み値を最小にすることである.この構成を完了する方法は2つあります.1つはkruskalアルゴリズムです.このアルゴリズムは、各エッジの重み値をソートし、小さなエッジを順番に選択してツリーに追加し、ツリーであることを保証します(つまり、ループを生成できません).もう1つはprimアルゴリズムであり,このアルゴリズムは点の観点から考えられる.まずmap[][2次元配列で2点間の重み値を格納し、1次元配列lowcost[]を使用して選択した点に関連付けられた重み値を格納し、mark[]配列を使用して使用した点をマークします.基本思想は最短経路におけるdijkstraアルゴリズムと非常に似ている.
primアルゴリズムの基本思想:
連通ネットワークN={V,E}からSを1点選択し、それに関連付けられ重み値が最も小さいエッジ(S,V)を選択し、その頂点を生成ツリーの頂点集合Uに加える.以降、各ステップは、頂点集合Uにない点を選択し、Uへの重み値を最小にし、頂点集合Uに追加する.このままでは、ネットワーク内のすべての頂点が生成ツリーの頂点集合Uに加わるまでである.
最小生成ツリーをprimアルゴリズムで構築するプロセス:
ツリーの頂点セットUとエッジセットが赤で、Uセット以外の点が青で、赤と青を結ぶエッジが紫であると仮定すると、最も短い紫のエッジが現在探しているエッジです.1つの頂点を選択するごとに残りの頂点を調整し、ツリーの頂点セットUまでの距離を更新します.具体的には、コードを参照してください.

#include
#include
#define INF 0x3f3f3f3f
int map[1010][1010];
int lowcost[1010];
int mark[1010];
int n,m;
int prim()
{
	int vir,min,sum=0;
	for(int i=1;i<=n;i++)			//         0，lowcost       1        
	{
		mark[i]=0;
		lowcost[i]=map[1][i];
	}
	mark[1]=1;						//      
	for(int i=1;imap[vir][j])
			{
				lowcost[j]=map[vir][j];
			}
		}
	}
	return sum;						//           
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)	// map           
				map[i][j]=INF;
		for(int i=0;icost)		//      ，          
			{
				map[x][y]=cost;
				map[y][x]=cost;
			}
		}
		printf("%d
",prim());		//            
	}
	return 0;
}