¿Qué es el algoritmo de Prim?
El algoritmo de Prim se utiliza para encontrar el árbol de expansión mínimo de un gráfico no dirigido
Supongamos que el gráfico G = (V, E) tiene un árbol de expansión y su conjunto de vértices es Ud.
①.Ponga v0 en U.
②.Encuentre una arista de peso mínimo entre todas las aristas (u, v) ∈ E con u ∈ U y v ∈ V-U para sumar el árbol de expansión.
③.Agregue v del borde que se encuentra en ② al conjunto de U. Si el conjunto de U ya tiene n elementos, finalice; de lo contrario, continúe con ②.
La complejidad temporal de su algoritmo es O(n^2)
Implementación del algoritmo Prim:
(1) Conjunto: establece un conjunto de matrices[i ] (i=0, 1,..., n-1), el valor inicial es 0, lo que significa que el vértice correspondiente no está en el conjunto (Nota: la diferencia entre el número de vértices y el número de subíndices es 1)
(2) El gráfico está representado por una matriz de vecinos. La ruta no está generalizada al infinito y puede ser reemplazada por números enteros grandes en las computadoras.
Programa de referencia
/* Prim.c
Copyright (c) 2002, 2006 por ctu_85
Todos los derechos reservados. p>
*/
/* La influencia de la existencia de puntos de conexión se puede omitir en el algoritmo de Prim, pero no se puede omitir en el algoritmo de Kruskal*/
#include "stdio. h"
#define maxver 10
#define maxright 100
int main()
{
int G[maxver][maxver], in[maxver]=, ruta[maxver][2]
int i, j, k, min=maxright
;int v1, v2, num, temp, status=0, start=0;
restart:
printf("Ingrese el número de vértices en el gráfico:\n" );
scanf(" d", amp; num);
if(numgt; maxver||numlt; 0)
{
printf("¡Error! ¡Ingrese!\n");
ir a reiniciar
}
for(j= 0; jlt; número; j )
for(k=0; klt; número; k )
{
si(j==k)
G[j][k]=maxright;
else
if(jlt;k)
G[j][k ]=maxright;
else
if(jlt;k)
{
re：
printf ("Ingrese el derecho entre el vértice d y el vértice d, si no existe ningún borde, ingrese -1：\n",j 1,k 1);
scanf("d ",amp; temp) ;
if(tempgt;=maxright||templt;-1)
{
printf("¡Entrada no válida! \n");
ir a re;
}
if(temp ==-1)
temp=maxright;
G[j][k]=G[k][j]=temp;
}
}
for(j =0;jlt;num;j )
{
status=0;
for(k=0;klt;num;k )
if(G[j][k]lt; maxright)
{
status=1;
romper;
}
if(status==0)
romper;
}
hacer
{
printf("Ingrese el vértice inicial del algoritmo de Prim: ");
("d",amp;start);
}mientras (startlt;0||startgt;num);
in[start-1]=1;
para(i=0;ilt;num-1amp;amp;status;i )
{
para(j=0;jlt;num;j )
for(k=0;klt;num;k)
if(G[j][k]lt;minamp;amp;in[j]amp;amp;(!in [k]))
{
v1=j
v2=k
min=G [j][k; ];
}
if(!in[v2])
{
ruta[i][0]=v1;
ruta[i][1]=v2
en[v1]=1
en[v2]=1; p>min= maxright;
}
}
if(!status)
printf("No podemos ocuparnos de ello porque ¡el gráfico no está conectado! \n");
else
{
for(i=0; ilt; num-1; i )
printf("Ruta d: vértice d al vértice d\n", i 1, ruta[i][0] 1, ruta[i][1] 1);
}
retorno 1;
}
Algoritmo de Prim.
①.Ponga v0 en U.
②.Encuentre una arista (u, v)∈ E con u∈ U y v∈ V-U para agregarla al árbol de expansión. p>
③. Agrega el borde v que se encuentra en ② al conjunto U. Si el conjunto U ya tiene n elementos, finalice; de lo contrario, continúe con ②.
La complejidad temporal de este algoritmo es O(n^2)
Programa de referencia
/El algoritmo Prim lee el número de vértices (n), el número de bordes (m), el punto inicial y el peso del borde, y el punto inicial y el peso del borde, guárdelos en la matriz de adyacencia
//Ejemplo
/7. 12 (7 vértices y 12 aristas)
/1 2 2