algorithm
L'algorithme de Prim
Recherche…
Introduction à l'algorithme de Prim
Disons que nous avons 8 maisons. Nous voulons installer des lignes téléphoniques entre ces maisons. Le bord entre les maisons représente le coût de la mise en ligne entre deux maisons.
Notre tâche consiste à mettre en place des lignes de telle sorte que toutes les maisons soient connectées et que le coût de la configuration de la connexion soit minimal. Maintenant, comment trouvons-nous cela? Nous pouvons utiliser l'algorithme de Prim .
L'algorithme de Prim est un algorithme glouton qui trouve un arbre couvrant minimal pour un graphique non dirigé pondéré. Cela signifie qu'il trouve un sous-ensemble des arêtes qui forment un arbre qui inclut tous les noeuds, où le poids total de toutes les arêtes de l'arborescence est réduit. L'algorithme a été développé en 1930 par le mathématicien tchèque Vojtěch Jarník , puis redécouvert et republié par l'informaticien Robert Clay Prim en 1957 et Edsger Wybe Dijkstra en 1959. Il est également connu comme algorithme DJP, algorithme de Jarnik, algorithme Prim-Jarnik ou Prim-Dijsktra. algorithme .
Voyons maintenant les termes techniques en premier. Si nous créons un graphe, S en utilisant des nœuds et des arêtes d'un graphe non orienté G , alors S s'appelle un sous -graphe du graphe G. Maintenant, S sera appelé Spanning Tree si et seulement si:
- Il contient tous les nœuds de G.
- C'est un arbre, cela signifie qu'il n'y a pas de cycle et que tous les nœuds sont connectés.
- Il y a (n-1) arêtes dans l'arbre, où n est le nombre de nœuds dans G.
Il peut y avoir beaucoup de Spanning Tree dans un graphique. L' arbre Spanning Minimum d'un graphe non orienté pondéré est un arbre, de sorte que la somme du poids des arêtes est minimale. Nous allons maintenant utiliser l'algorithme de Prim pour trouver l'arbre de recouvrement minimal, c'est-à-dire comment configurer les lignes téléphoniques dans notre exemple de graphique de manière à ce que le coût d'installation soit minimal.
Au début, nous sélectionnerons un nœud source . Disons que node-1 est notre source . Maintenant, nous allons ajouter le bord de node-1 qui a le coût minimum à notre sous-graphe. Ici, nous marquons les bords qui sont dans le sous-graphe en utilisant la couleur bleue . Ici, 1-5 est notre avantage désiré. 
Nous considérons maintenant tous les bords de node-1 et node-5 et prenons le minimum. Puisque 1-5 est déjà marqué, nous prenons 1-2 . 
Cette fois, nous considérons le nœud 1 , le nœud 2 et le nœud 5 et prenons le bord minimal qui est 5-4 . 
La prochaine étape est importante. À partir du nœud 1 , du nœud 2 , du nœud 5 et du nœud 4 , le bord minimal est de 2 à 4 . Mais si nous sélectionnons celui-là, cela créera un cycle dans notre sous-graphe. Ceci est dû au fait que le noeud 2 et le noeud 4 sont déjà dans notre sous-graphe. Donc, prendre l'avantage 2-4 ne nous profite pas. Nous allons sélectionner les arêtes de manière à ajouter un nouveau noeud dans notre sous-graphe . Nous sélectionnons donc l'arête 4-8 . 
Si nous continuons ainsi, nous sélectionnerons l'arête 8-6 , 6-7 et 4-3 . Notre sous-graphe ressemblera à: 
Ceci est notre sous-graphe souhaité, qui nous donnera le spanning tree minimum. Si nous supprimons les arêtes que nous n'avons pas sélectionnées, nous obtiendrons: 
Ceci est notre arbre spanning minimum (MST). Le coût de la mise en place des connexions téléphoniques est donc le suivant: 4 + 2 + 5 + 11 + 9 + 2 + 1 = 34 . Et l'ensemble des maisons et leurs connexions sont montrés dans le graphique. Il peut y avoir plusieurs MST d'un graphique. Cela dépend du noeud source choisi.
Le pseudo-code de l'algorithme est donné ci-dessous:
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
Complexité:
La complexité temporelle de l'approche naïve ci-dessus est O (V²) . Il utilise une matrice de contiguïté. Nous pouvons réduire la complexité en utilisant la file d'attente prioritaire. Lorsque nous ajoutons un nouveau nœud à Vnew , nous pouvons ajouter ses bords adjacents dans la file d'attente prioritaire. Ensuite, sortez le bord pondéré minimum. La complexité sera alors: O (ElogE) , où E est le nombre d'arêtes. Encore une fois, un tas binaire peut être construit pour réduire la complexité à O (ElogV) .
Le pseudo-code utilisant Priority Queue est indiqué ci-dessous:
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
Ici key [] stocke le coût minimum de traverser node-v . parent [] est utilisé pour stocker le nœud parent. C'est utile pour parcourir et imprimer l'arbre.
Voici un programme simple en 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();
}
}
Compilez le code ci-dessus en utilisant javac Graph.java
Sortie:
$ 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