algorithm
프림의 알고리즘
수색…
Prim의 알고리즘 소개
우리 집이 8 개 있다고 가정 해 봅시다. 우리는이 집들 사이에 전화선을 설치하려고합니다. 집들 사이의 가장자리는 두 집 사이의 선을 설정하는 비용을 나타냅니다.
우리의 임무는 모든 주택이 연결되고 전체 연결을 설정하는 비용이 최소가되는 방식으로 회선을 설정하는 것입니다. 이제 우리가 어떻게 그걸 발견 할 수 있을까요? 우리는 Prim 's Algorithm을 사용할 수 있습니다.
Prim 's Algorithm 은 가중치가 부여 된 무 방향성 그래프에 대해 최소 스패닝 트리를 찾는 greedy 알고리즘입니다. 즉, 모든 노드를 포함하는 트리를 형성하는 모서리의 하위 집합을 찾아 트리의 모든 모서리의 총 무게가 최소화됩니다. 이 알고리즘은 1930 년 체코의 수학자 Vojtěch Jarní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를 사용 합니다. 
이번에는 node-1 , node-2 및 node-5 를 고려하여 5-4 의 최소 에지를 취합니다. 
다음 단계는 중요합니다. node-1 , node-2 , node-5 및 node-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²) 입니다. 그것은 인접 행렬을 사용합니다. 우선 순위 큐를 사용하여 복잡성을 줄일 수 있습니다. 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 [] 는 노드 -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 사용하여 위의 코드를 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