algorithm
Algoritmo di Prim
Ricerca…
Introduzione all'algoritmo di Prim
Diciamo che abbiamo 8 case. Vogliamo impostare le linee telefoniche tra queste case. Il confine tra le case rappresenta il costo della linea di confine tra due case.
Il nostro compito è impostare le linee in modo tale che tutte le case siano collegate e il costo per impostare l'intera connessione sia minimo. Ora, come lo scopriamo? Possiamo usare l'algoritmo di Prim .
L'algoritmo di Prim è un algoritmo avido che trova uno spanning tree minimo per un grafo non orientato ponderato. Ciò significa che trova un sottoinsieme dei bordi che forma un albero che include ogni nodo, in cui viene ridotto al minimo il peso totale di tutti i bordi dell'albero. L'algoritmo è stato sviluppato nel 1930 dal matematico ceco Vojtěch Jarník e successivamente riscoperto e ripubblicato dallo scienziato informatico Robert Clay Prim nel 1957 e Edsger Wybe Dijkstra nel 1959. È anche conosciuto come algoritmo DJP , algoritmo di Jarnik, algoritmo Prim-Jarnik o Prim-Dijsktra. algoritmo .
Ora osserviamo prima i termini tecnici. Se creiamo un grafico, S utilizzando alcuni nodi e bordi di un grafo non orientato G , allora S è chiamato sottografo del grafico G. Ora S sarà chiamato Spanning Tree se e solo se:
- Contiene tutti i nodi di G.
- È un albero, significa che non c'è un ciclo e tutti i nodi sono collegati.
- Ci sono i bordi (n-1) nell'albero, dove n è il numero di nodi in G.
Ci possono essere molti Spanning Tree di un grafico. L' albero spanning minimo di un grafo orientato ponderato è un albero, tale che la somma del peso dei bordi è minima. Ora utilizzeremo l'algoritmo di Prim per scoprire l'albero di copertura minimo, ovvero come impostare le linee telefoniche nel nostro grafico di esempio in modo tale che il costo di configurazione sia minimo.
Inizialmente selezioneremo un nodo di origine . Diciamo che il nodo 1 è la nostra fonte . Ora aggiungeremo il bordo dal nodo 1 che ha il costo minimo per il nostro sottografo. Qui segniamo i bordi che si trovano nel sottografo usando il colore blu . Qui 1-5 è il nostro lato desiderato. 
Ora consideriamo tutti i bordi dal nodo 1 e dal nodo 5 e prendiamo il minimo. Poiché 1-5 è già segnato, prendiamo 1-2 . 
Questa volta, consideriamo nodo-1 , nodo-2 e nodo-5 e prendiamo il bordo minimo che è 5-4 . 
Il prossimo passo è importante. Dal nodo 1 , dal nodo 2 , dal nodo 5 e dal nodo 4 , il bordo minimo è 2-4 . Ma se lo selezioniamo, creerà un ciclo nel nostro sottografo. Questo perché il nodo 2 e il nodo 4 sono già nel nostro sottografo. Quindi il vantaggio 2-4 non ci avvantaggia. Selezioneremo i bordi in modo tale da aggiungere un nuovo nodo nel nostro sottografo . Quindi selezioniamo il bordo 4-8 . 
Se continuiamo in questo modo, selezioneremo il bordo 8-6 , 6-7 e 4-3 . Il nostro sottografo sarà simile a: 
Questo è il nostro sottografo desiderato, che ci darà l'albero spanning minimo. Se rimuoviamo i bordi che non abbiamo selezionato, otterremo: 
Questo è il nostro spanning tree minimo (MST). Quindi il costo per impostare le connessioni telefoniche è: 4 + 2 + 5 + 11 + 9 + 2 + 1 = 34 . E l'insieme di case e le loro connessioni sono mostrati nel grafico. Possono esserci più MST di un grafico. Dipende dal nodo sorgente che scegliamo.
Di seguito è riportato lo pseudo-codice dell'algoritmo:
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
Complessità:
La complessità temporale dell'approccio ingenuo di cui sopra è O (V²) . Usa la matrice di adiacenza. Possiamo ridurre la complessità usando la coda di priorità. Quando aggiungiamo un nuovo nodo a Vnew , possiamo aggiungere i suoi bordi adiacenti nella coda di priorità. Quindi estrarre il bordo ponderato minimo da esso. Quindi la complessità sarà: O (ElogE) , dove E è il numero di spigoli. Di nuovo un heap binario può essere costruito per ridurre la complessità a O (ElogV) .
Lo pseudo-codice che utilizza la coda di priorità è indicato di seguito:
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
Qui la chiave [] memorizza il costo minimo del nodo di movimento -v . parent [] viene utilizzato per memorizzare il nodo genitore. È utile per attraversare e stampare l'albero.
Di seguito è riportato un semplice programma in 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();
}
}
Compilare il codice sopra utilizzando javac Graph.java
Produzione:
$ 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