Автор оригинала: Pankaj Kumar.
Минимальное связующее дерево, также известное как связующее дерево минимального веса, представляет собой подмножество ребер связного неориентированного графа, взвешенного по ребрам. Это подмножество соединяет все вершины вместе, без каких-либо циклов и с минимально возможным общим весом ребер.
Для графика может быть более одного минимального связующего дерева. Однако общая стоимость будет одинаковой для разных MST одного и того же дерева.
Алгоритм Прима
Алгоритм Прима-это жадный алгоритм, который находит MST для взвешенного неориентированного графика.
Алгоритм выполняется путем построения НЕ более одной вершины за раз из произвольной начальной вершины. На каждом этапе он делает наиболее экономичный выбор. То есть он оптимизируется локально для достижения глобального оптимума.
Алгоритм Прима работает следующим образом:
- Инициализируйте минимальное связующее дерево случайной вершиной (начальной вершиной).
- Найдите все ребра, которые соединяют дерево с новыми вершинами, найдите минимум и добавьте его в дерево (жадный выбор).
- Продолжайте повторять шаг 2, пока мы не получим минимальное связующее дерево (пока не будут достигнуты все вершины).
Мы можем посмотреть на пример, чтобы понять, как работает алгоритм Prim.
Пусть взвешенный неориентированный график выглядит следующим образом:
Мы выбираем 0 в качестве начальной вершины.
В качестве следующего шага мы выбираем минимум из всех узлов, связанных с НАИБОЛЬШИМ КОЛИЧЕСТВОМ.
На каждом последующем этапе мы находим ребро с минимальной стоимостью, которое соединяет дерево с новой вершиной.
край: 0-1 край: 1-4 край: 4-2 край: 1-3
Используя 4 ребра, мы соединили все 5 узлов. Стоимость минимального связующего дерева равна сумме всех весов ребер.
В этом примере это:
4+1+6+2 = 13
Java-код алгоритма Прима
Реализация java выглядит следующим образом.
Код для класса графиков:
package com.JournalDev;
import java.util.*;
public class Graph
{
// Representation of the graph
private static int infinite = 9999999;
int[][] LinkCost; // graph matrix
int num_nodes; // number of nodes
// constructor takes in a matrix as its input
Graph(int[][] mat)
{
int i, j;
num_nodes = mat.length;
LinkCost = new int[num_nodes][num_nodes];
// copying the weights to LinkCost matrix
for ( i=0; i < num_nodes; i++)
{
for ( j=0; j < num_nodes; j++)
{
LinkCost[i][j] = mat[i][j];
if ( LinkCost[i][j] == 0 )
LinkCost[i][j] = infinite;
}
}
}
//function to get the nodes that are unreached
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[num_nodes]; // array to keep track of the reached nodes
int[] predNode = new int[num_nodes]; // array to maintain min cost edge
// starting vertex
Reached[0] = true;
//setting other vertices as unreached
for ( k = 1; k < num_nodes; k++ )
{
Reached[k] = false;
}
predNode[0] = 0; // No edge for node 0
printCoveredNodes( Reached );
//we iterate for n-1 nodes that haven't been reached yet
for (k = 1; k < num_nodes; k++)
{
x = y = 0;
for ( i = 0; i < num_nodes; i++ )
for ( j = 0; j < num_nodes; j++ )
{
//update the MST with the minimum cost Link
if ( Reached[i] && !Reached[j] &&
LinkCost[i][j] < LinkCost[x][y] )
{
x = i;
y = j;
}
}
System.out.println("Next selected edge: (" +
+ x + "," +
+ y + ")" +
" cost = " + LinkCost[x][y]);
predNode[y] = x; // add the min cost link to predNode
Reached[y] = true;
printCoveredNodes( Reached );
System.out.println();
}
printMinCostEdges( predNode );
}
// function to print the edges of spanning tree
void printMinCostEdges( int[] a )
{
System.out.println("Edges in MST: ");
for ( int i = 0; i < num_nodes; i++ )
System.out.println( a[i] + " --> " + i );
}
void printCoveredNodes(boolean[] Reached )
{
System.out.print("Covered Nodes = ");
for (int i = 0; i < Reached.length; i++ )
if ( Reached[i] )
System.out.print( i + " ");
System.out.println();
}
}
Основной класс:
package com.JournalDev;
public class Main {
public static void main(String[] args) {
int[][] conn = {{0, 4, 0, 0, 5},
{4, 0, 3, 6, 1},
{0, 3, 0, 6, 2},
{0, 6, 6, 0, 7},
{5, 1, 2, 7, 0},
};
Graph G = new Graph(conn);
G.Prim();
}
}
Выход
Мы можем проверить вывод, используя приведенный выше пример.
Вывод
Этот учебник был посвящен алгоритму Прима, чтобы найти минимальное связующее дерево для неориентированных взвешенных графиков. Надеюсь, вам понравилось изучать алгоритм Прим.