primアルゴリズムc++実装

1.概要
G=(V,E)を無方向連通帯域重み図、すなわちネットワークとする.Eの各エッジ(v,w)の重みはc[v][w]である.GのサブマップG’がGのすべての頂点を含むツリーである場合、G’をGの生成ツリーと呼ぶ.生成ツリー上の各エッジ権の合計を、その生成ツリーの消費と呼びます.Gのすべての生成ツリーのうち、最も消費が少ない生成ツリーをGの最小生成ツリーと呼ぶ.
ネットワークの最小生成ツリーは実際に広く応用されている.例えば、通信ネットワークを設計する際、図の頂点で都市を表し、エッジ(v,w)の重みc[v][w]で都市vと都市wとの間の通信回線を構築するのに要する費用を表すと、最小生成ツリーは通信ネットワークを構築する最も経済的なスキームを与える.
最小生成ツリーの性質:
G=(V,E)を連通帯域重みマップ,UをVの真サブセットとする.(u,v)がEに属し、uがUに属し、vがV−Uに属し、このようなエッジのすべてにおいて、(u,v)の重みc[u][v]が最小である場合、(u,v)を1つのエッジとするGの最小生成ツリーが必ず存在する.この性質はMST性質とも呼ばれることがある.
 
2.PRIMアルゴリズム
G=(V,E)を連通帯権図とし,V={1,2,...,n}とする.
Gの最小生成ツリーを構築するPrimアルゴリズムの基本思想は、まずS={1}を置き、次に、SがVの真のサブセットである限り、条件iがSに属し、jがV−Sに属し、c[i][j]が最小であるエッジを選択し、頂点jをSに追加することである.このプロセスはS=Vのときまで行われる.
この過程で選択されたすべてのエッジは、Gの最小生成ツリーを構成するのに適している.
最小生成木の性質と数学的帰納法により,上記アルゴリズムにおけるエッジ集合Tは常にGのある最小生成木におけるエッジを含むことが容易に証明される.したがって,アルゴリズム終了時には,T中のすべての辺がGの1本の最小生成木を構成する.
例えば、右図の重み付き図について、Primアルゴリズムに従ってエッジを選択する手順を以下のページ図に示す.　　
Primアルゴリズムでエッジを選択する手順を次のページに示します.
上記のPrimアルゴリズムでは、条件iがSにあり、jもV−Sにあり、重みc[i][j]が最も小さいエッジ(i,j)をどのように効率的に見つけるかも考慮すべきである.この目的を達成するより簡単な方法は,2つの配列closestとlowcostを設定することである.
Primアルゴリズムの実行中に、まずV-Sでlowcost値を最小にする頂点jを見つけ、配列closestに基づいてエッジ(j,closest[j])を選択し、最後にjをSに追加し、closestとlowcostに必要な修正を行う.
この方法で実現するPrimアルゴリズムに必要な計算時間はO(n 2)である.
実はこのアルゴリズムはディジェストラアルゴリズムとよく似ていて、毎回現在知られている未連通ノードに到達する最小の重み値を取り、その点を加えた後にlowcost配列とclosest配列をリフレッシュし、ツリーに参加していない点がこの木に追加されたばかりの点を通じてより短い経路であるより小さな重み値があるかどうかを比較して、あればリフレッシュします.ない場合は処理しないで、lowcostとclosest配列のデータが現在知られている状況に基づいて得られた最小重み配列とその頂点に最も近い頂点番号であることを保証します.
図は運搬しているので、自分でやるのがおっくうだからです.
コードは次のとおりです.

#include
#include
using namespace std;
void prim(vector> &VGraph, vector &lowcost, vector &closest, vector &visited)  //            
{
	int size = lowcost.size();
	visited[0] = true;
	for (int i = 1; i < size; i++)
	{
		lowcost[i] = VGraph[0][i];
		closest[i] = 0;
		visited[i] = false;
	}
	cout << "0";
	int weight = 0;
	for (int i = 0; i < size; i++)
	{
		int min = 99999;
		int index = 1;
		for (int j = 0; j < size; j++)
		{
			if (lowcost[j] < min&&!visited[j])
			{
				min = lowcost[j];
				index = j;
			}
		}
		if (index == 1 && min == 99999)
		{
			cout << "
        :" << weight< " << index;
		visited[index] = true;
		for (int j = 1; j >M>>N;
	vector> VGraph(M);
	vector lowcost(M);
	vector closest(M);
	vector visited(M);
	for (int i = 0; i < M; i++)
	{
		VGraph[i].resize(M);
	}
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < M; j++)
		{
			VGraph[i][j] = 99999;
		}
	}
	for (int i = 0; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		int length;
		cin >> length;
		VGraph[a][b] = VGraph[b][a] = length;
	}
	prim(VGraph, lowcost, closest, visited);
}