algorithm
Алгоритм Прима
Поиск…
Введение в алгоритм Прима
Допустим, у нас 8 домов. Мы хотим установить телефонные линии между этими домами. Краем между домами является стоимость установки линии между двумя домами.
Наша задача - настроить линии таким образом, чтобы все дома были подключены, а стоимость настройки всего соединения минимальна. Теперь, как мы это выясним? Мы можем использовать алгоритм Прима .
Алгоритм Прима - жадный алгоритм, который находит минимальное связующее дерево для взвешенного неориентированного графа. Это означает, что он находит подмножество ребер, которые образуют дерево, которое включает в себя каждый узел, где общий вес всех ребер в дереве минимизируется. Алгоритм был разработан в 1930 году чешским математиком Войтехом Ярником, а затем вновь открыт и переиздан компьютерным ученым Робертом Клеем Примом в 1957 году и Эдсгером Вибе Дикстром в 1959 году. Он также известен как алгоритм DJP, алгоритм Ярника, алгоритм Прима-Ярника или Прим-Дижсктра алгоритм .
Теперь давайте сначала рассмотрим технические термины. Если мы создадим граф, S используя некоторые узлы и ребра неориентированного графа G , то S называется подграфом графа G. Теперь S будет называться Spanning Tree тогда и только тогда, когда:
- Он содержит все узлы группы G.
- Это дерево, это означает, что нет цикла, и все узлы связаны.
- В дереве есть (n-1) ребра, где n - число узлов в G.
На графике может быть много Spanning Tree . Минимальное связующее дерево взвешенного неориентированного графа - это дерево, так что сумма веса ребер минимальна. Теперь мы будем использовать алгоритм 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²) . Он использует матрицу смежности. Мы можем уменьшить сложность с помощью очереди приоритетов. Когда мы добавляем новый узел в Vnew , мы можем добавить его соседние ребра в очереди приоритетов. Затем вытащите минимальный взвешенный край из него. Тогда сложность будет: O (ElogE) , где E - количество ребер. Снова можно построить двоичную кучу, чтобы уменьшить сложность до O (ElogV) .
Псевдокод с использованием очереди приоритетов приведен ниже:
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
Здесь ключ [] хранит минимальную стоимость перемещения узла-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