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

プリムアルゴリズム(Primアルゴリズム)、図論のアルゴリズムで、重み付け連通図の中で最小生成ツリーを検索することができる.すなわち、このアルゴリズムによって探索されたエッジサブセットからなるツリーには、連通図のすべての頂点だけでなく、そのすべてのエッジの重み値の和も最小である.
ウィキペディアの定義を借りると、
単一の頂点から、プリムアルゴリズムは、連通図のすべての頂点に及ぶまで、ツリーに含まれる頂点の数を徐々に拡大します.
入力:頂点セットがV、エッジセットがEの重み付け連通図.
初期化:Vnew={x}であり、xは集合Vのいずれかのノード(開始点)、Enew={}である.
Vnew=Vになるまで、次の操作を繰り返します.
集合Eでは、重み値が最も小さいエッジ(u,v)が選択され、uは集合Vnewの要素であり、vはVにVnewが加わっていない頂点である(前述の条件を満たす同じ重み値を有するエッジが複数存在する場合、いずれかを任意に選択することができる).
集合Vnewにvを加え,(u,v)を集合Enewに加える.
出力:得られた最小生成ツリーは、集合VnewおよびEnewを用いて記述される.
実はアルゴリズムの基本思想は1つの貪欲な概念で、1つのノードを選択してソースノードとして拡張して、拡張方法はソースノードと他のノードの間の重み値が最も小さいノードを選択して、もし1つの最小生成木を構築して必ずソースノードを含んで、ソースノードを含むならば必ずソースノードに最も近い辺を選んで含むためです.その後、1つのノードを選択する最小生成ツリーの集合を構成し、すべてのノードを2つの部分に分割する、ループごとに最小生成ツリーの集合が1つ増加するのでverNum-1をループするだけで最終結果が得られる.
ここで継続的に維持するのは、ノードをフィルタリングする際に使用される最小エッジの配列lowcost、すなわち、集合から他のノードまでの最小エッジ長であり、集合に選択するノードiのlowcost[i]には0が付与される.ループごとにminを選択するプロセスは、優先キューを用いて実現することができ、自動的にソートすることができ、毎回デキューするだけでよい.

typedef struct {
    int arc[MAXVEX][MAXVEX];
    int numVertexes;
}MGraph;

void prim(MGraph G)
{
	int i,j;//    
	int min;//             
	int k;//           
	int adjvex[MAXVEX];//              , adjvex[2] = 4;          2   4.
	int lowcost[MAXVEX];//                      .
	lowcost[0] = 0;//        0                
	adjvex[0] = 0;//  0   0     ,  adjvex[0] = 0.

	for (i = 0; i < G.numVertexes; i++)//   ,  0              
	{
		lowcost[i] = G.arc[0][i];
		adjvex[i] = 0;
	}

	for (i = 1; i < G.numVertexes; i++)// 1        ,                    
	{
		min = INFINITY;
		j = 1;
		k = 0;

		while(j < G.numVertexes)//              
		{
			if (lowcost[j]!=0&&lowcost[j]<min)//lowcost=0          
			{
				min = lowcost[j];//       
				k = j;//           
			}
			j++;
		}

		cout << "(" << adjvex[k] << ", " << k << ")" << "  "; //               
        lowcost[k] = 0;//            0,           

		for(j = 1; j < G.numVertexes; j++)//       ,  lowcost  .
		{
			if(lowcost[j]!=0&&G.arc[k][j] < lowcost[j])
			{
				lowcost[j] = G.arc[k][j];
				adjvex[j] = k;
			}
		}
	}
}