primアルゴリズム擬似コード

クリックしてリンクを開く
Primアルゴリズム
1.概要
プリムアルゴリズム(Primアルゴリズム)、図論のアルゴリズムで、重み付け連通図の中で最小生成ツリーを検索することができる.すなわち、このアルゴリズムによって探索されたエッジサブセットからなるツリーには、連通図のすべての頂点(英語:Vertex(graph theory))だけでなく、そのすべてのエッジの重み値の和も最小である.このアルゴリズムは1930年にチェコの数学者ヴォイシェハ・アルニク(英語:Vojtěch Jarník)発見;1957年にアメリカのコンピュータ科学者ロバート・プリム(英語:Robert C.Prim)が独立して発見した.1959年、エズグ・ディコスチャーは再びこのアルゴリズムを発見した.したがって、場合によっては、プリムアルゴリズムはDJPアルゴリズム、アルニクアルゴリズム、またはプリム−アルニクアルゴリズムとも呼ばれる.
 
2.アルゴリズムの簡単な説明
1).入力:頂点セットがV、エッジセットがEの重み付け連通図.
2).初期化:Vnew={x}であり、xは集合Vのいずれかのノード(開始点)、Enew={}であり、空である.
3).Vnew=Vになるまで、次の操作を繰り返します.
a.集合Eにおいて重み値が最も小さいエッジを選択し、uは集合Vnewの要素であり、vはVnewの集合になく、v∈V(前述の条件を満たす同じ重み値を有するエッジが複数存在する場合、任意にそのうちの1つを選択することができる).
b.vを集合Vnewに加え、辺を集合Enewに加える.
4).出力:得られた最小生成ツリーは、集合VnewおよびEnewを用いて記述される.
 

#define MAX  100000
#define VNUM  10+1                                             //    ID 0  ,so id   1~10

int edge[VNUM][VNUM]={/*       */};
int lowcost[VNUM]={0};                                         //  Vnew     V        
int addvnew[VNUM];                                             //        Vnew
int adjecent[VNUM]={0};                                        //  V  Vnew     


void prim(int start)
{
     int sumweight=0;
     int i,j,k=0;

     for(i=1;i