algorithm
プリムのアルゴリズム
サーチ…
プリムのアルゴリズムの紹介
私たちに8軒の家があるとしよう。これらの家の間に電話回線を設置したい。家の間のエッジは、2つの家の間の線を設定するコストを表します。
私たちの仕事は、すべての住宅が接続され、接続全体を設定するコストが最小限になるように回線を設定することです。今、それをどのように見つけ出すのですか？ プリムのアルゴリズムを使うことができます。
Prim's Algorithmは、重み付けされた無向グラフの最小スパニングツリーを見つけるグリーディアルゴリズムです。これは、ツリー内のすべてのエッジの総重量が最小になるすべてのノードを含むツリーを形成するエッジのサブセットを見つけることを意味します。このアルゴリズムは1930年にチェコの数学者VojtěchJarníkによって開発され、1957年にコンピュータ科学者のRobert Clay Primと1959年にEdsger Wybe Dijkstraによって再発見され、再公開されました。DJP アルゴリズム 、 Jarnikアルゴリズム 、 Prim-JarnikアルゴリズムまたはPrim-Dijsktraアルゴリズム 。
さて、最初に技術用語を見てみましょう。無向グラフGのいくつかのノードとエッジを使ってグラフSを作成すると、 SはグラフGの 部分グラフと呼ばれます。今の場合、 Sはスパニングツリーと呼ばれます。
- それはGのすべてのノードを含んでいます。
- これはツリーであり、サイクルがなく、すべてのノードが接続されていることを意味します。
- ツリー内には（n-1）個の辺があり、 nはG内のノードの数です。
スパニングツリーにはグラフがたくさんあることがあります。重み付き無向グラフの最小スパニングツリーは、エッジの重みの合計が最小となるようなツリーです。ここでは、 Primのアルゴリズムを使用して最小スパニングツリーを見つけます。つまり、セットアップのコストが最小になるように電話線を設定する方法です。
最初にソースノードを選択します。 ノード1が私たちのソースだとしましょう。ここでは、最小コストを持つノード1からサブグラフにエッジを追加します。ここでは、サブグラフ内の辺をカラーの青でマークします。ここで1-5が私たちの望むエッジです。 
ここでは、 ノード1とノード5のすべてのエッジを考慮し、最小値をとります。 1-5は既にマークされているので、私たちは1-2を取る。 
今回は、 ノード 1 、 ノード2 、 ノード5を考慮し、最小エッジを5-4とする 。 
次のステップは重要です。 ノード1 、 ノード2 、 ノード5およびノード4から、最小エッジは2-4である 。しかし、それを選択すると、サブグラフにサイクルが作成されます。これは、 ノード2とノード4が既にサブグラフ内にあるためです。だから、 2-4のエッジを取っても私たちの利益にはならない。 サブグラフに新しいノードを追加するような方法でエッジを選択します 。そこで、エッジ4-8を選択します。 
私たちはこの方法を継続した場合、我々はエッジ8-6、6-7と4-3を選択します。私たちのサブグラフは次のようになります： 
これは私たちの望むサブグラフで、最小限のスパニングツリーを与えます。選択しなかったエッジを削除すると、次のようになります。 
これが最小スパニングツリー （MST）です。したがって、電話接続を設定するコストは、 4 + 2 + 5 + 11 + 9 + 2 + 1 = 34です。そして、家とそのつながりのセットがグラフに表示されます。グラフのMSTは複数ある場合があります。選択したソースノードによって異なります。
アルゴリズムの疑似コードを以下に示します。
Procedure PrimsMST(Graph): // here Graph is a non-empty connected weighted graph
Vnew[] = {x} // New subgraph Vnew with source node x
Enew[] = {}
while Vnew is not equal to V
u -> a node from Vnew
v -> a node that is not in Vnew such that edge u-v has the minimum cost
// if two nodes have same weight, pick any of them
add v to Vnew
add edge (u, v) to Enew
end while
Return Vnew and Enew
複雑：
上記の単純なアプローチの時間の複雑さはO（V 2）です。それは隣接行列を使用します。優先度キューを使用して複雑さを減らすことができます。 Vnewに新しいノードを追加すると、隣接するエッジを優先キューに追加できます。それから最小重み付きエッジをポップします。複雑さはO（ElogE）となります.Eはエッジの数です。複雑さをO（ElogV）に減らすために、やはりバイナリヒープを構築することができます。
Priority Queueを使用した擬似コードは次のとおりです。
Procedure MSTPrim(Graph, source):
for each u in V
key[u] := inf
parent[u] := NULL
end for
key[source] := 0
Q = Priority_Queue()
Q = V
while Q is not empty
u -> Q.pop
for each v adjacent to i
if v belongs to Q and Edge(u,v) < key[v] // here Edge(u, v) represents
// cost of edge(u, v)
parent[v] := u
key[v] := Edge(u, v)
end if
end for
end while
ここで、 key []は、 node-vを通過する最小コストを格納します 。 parent []は、親ノードを格納するために使用されます。ツリーを横断して印刷するのに便利です。
以下はJavaの簡単なプログラムです：
import java.util.*;
public class Graph
{
private static int infinite = 9999999;
int[][] LinkCost;
int NNodes;
Graph(int[][] mat)
{
int i, j;
NNodes = mat.length;
LinkCost = new int[NNodes][NNodes];
for ( i=0; i < NNodes; i++)
{
for ( j=0; j < NNodes; j++)
{
LinkCost[i][j] = mat[i][j];
if ( LinkCost[i][j] == 0 )
LinkCost[i][j] = infinite;
}
}
for ( i=0; i < NNodes; i++)
{
for ( j=0; j < NNodes; j++)
if ( LinkCost[i][j] < infinite )
System.out.print( " " + LinkCost[i][j] + " " );
else
System.out.print(" * " );
System.out.println();
}
}
public int unReached(boolean[] r)
{
boolean done = true;
for ( int i = 0; i < r.length; i++ )
if ( r[i] == false )
return i;
return -1;
}
public void Prim( )
{
int i, j, k, x, y;
boolean[] Reached = new boolean[NNodes];
int[] predNode = new int[NNodes];
Reached[0] = true;
for ( k = 1; k < NNodes; k++ )
{
Reached[k] = false;
}
predNode[0] = 0;
printReachSet( Reached );
for (k = 1; k < NNodes; k++)
{
x = y = 0;
for ( i = 0; i < NNodes; i++ )
for ( j = 0; j < NNodes; j++ )
{
if ( Reached[i] && !Reached[j] &&
LinkCost[i][j] < LinkCost[x][y] )
{
x = i;
y = j;
}
}
System.out.println("Min cost edge: (" +
+ x + "," +
+ y + ")" +
"cost = " + LinkCost[x][y]);
predNode[y] = x;
Reached[y] = true;
printReachSet( Reached );
System.out.println();
}
int[] a= predNode;
for ( i = 0; i < NNodes; i++ )
System.out.println( a[i] + " --> " + i );
}
void printReachSet(boolean[] Reached )
{
System.out.print("ReachSet = ");
for (int i = 0; i < Reached.length; i++ )
if ( Reached[i] )
System.out.print( i + " ");
//System.out.println();
}
public static void main(String[] args)
{
int[][] conn = {{0,3,0,2,0,0,0,0,4}, // 0
{3,0,0,0,0,0,0,4,0}, // 1
{0,0,0,6,0,1,0,2,0}, // 2
{2,0,6,0,1,0,0,0,0}, // 3
{0,0,0,1,0,0,0,0,8}, // 4
{0,0,1,0,0,0,8,0,0}, // 5
{0,0,0,0,0,8,0,0,0}, // 6
{0,4,2,0,0,0,0,0,0}, // 7
{4,0,0,0,8,0,0,0,0} // 8
};
Graph G = new Graph(conn);
G.Prim();
}
}
javac Graph.javaを使用して上記のコードをコンパイルします。
出力：
$ java Graph
* 3 * 2 * * * * 4
3 * * * * * * 4 *
* * * 6 * 1 * 2 *
2 * 6 * 1 * * * *
* * * 1 * * * * 8
* * 1 * * * 8 * *
* * * * * 8 * * *
* 4 2 * * * * * *
4 * * * 8 * * * *
ReachSet = 0 Min cost edge: (0,3)cost = 2
ReachSet = 0 3
Min cost edge: (3,4)cost = 1
ReachSet = 0 3 4
Min cost edge: (0,1)cost = 3
ReachSet = 0 1 3 4
Min cost edge: (0,8)cost = 4
ReachSet = 0 1 3 4 8
Min cost edge: (1,7)cost = 4
ReachSet = 0 1 3 4 7 8
Min cost edge: (7,2)cost = 2
ReachSet = 0 1 2 3 4 7 8
Min cost edge: (2,5)cost = 1
ReachSet = 0 1 2 3 4 5 7 8
Min cost edge: (5,6)cost = 8
ReachSet = 0 1 2 3 4 5 6 7 8
0 --> 0
0 --> 1
7 --> 2
0 --> 3
3 --> 4
2 --> 5
5 --> 6
1 --> 7
0 --> 8
