Algoritmo MST de Prim en O (| V |^2)

Complejidad de tiempo de El algoritmo MST de Prim. es O(|V|^2) si usa una representación de matriz de adyacencia.Algoritmo MST de Prim en O (| V |^2)

Estoy tratando de implementar el algoritmo de Prim usando una matriz de adyacencia. Estoy usando this como referencia.

V = {1,2...,n} 
U = {1} 
T = NULL 
while V != U: 

    /* 
     Now this implementation means that 
     I find lowest cost edge in O(n). 
     How do I do that using adjacency list? 
    */ 

    let (u, v) be the lowest cost edge 
       such that u is in U and v is in V - U; 

    T = T + {(u,v)} 
    U = U + {v}

EDIT:

entiendo algoritmo de Prim muy bien.
Sé cómo implementarlo de manera eficiente usando montones y colas de prioridad.
También sé sobre mejores algoritmos.
Quiero usar la representación de matriz de adyacencia del gráfico y obtener la implementación O (| V |^2).

QUIERO LA APLICACIÓN AVERÍA

Fuente

2010-08-06 Pratik Deoghare

Aquí está la implementación V^2 hacia el final de la página http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/primAlgor.htm – Ankush

lo hace como en Dijkstra's algorithm, seleccionando el nodo que está conectado a su árbol parcial actual con el borde de coste mínimo (que no genera un ciclo) . Creo que wikipedia explica Prim mejor que ese pseudocódigo que tienes. Dale un vistazo y avísame si tienes más preguntas.

Fuente

2010-08-06 10:21:26 IVlad

El problema no es entender el algoritmo. Lo entiendo bastante bien. El problema no es una implementación eficiente. Hay muchos que usan colas de prioridad. El problema es cómo lo implemento con exactamente la complejidad O (| V |^2). –

Encontrar el borde más bajo costo (u, v), de manera que u es en U y v es en V-U, se hace con una cola de prioridad . Más precisamente, la cola de prioridad contiene cada nodo v de V-U junto con el límite de costo más bajo de v en el árbol actual U. En otras palabras, la cola contiene exactamente | V-U | elementos.

Después de añadir un nuevo nodo u a T, tiene que actualizar la cola de prioridad mediante la comprobación de los nodos vecinos de u pueden ahora ser alcanzados por un borde de costo más bajo que antes.

La elección de la cola de prioridad determina la complejidad del tiempo. Obtendrá O (| V |^2) implementando la cola de prioridad como una matriz simple cheapest_edges[1..|V|]. Esto se debe a que encontrar el mínimo en esta cola toma O (| V |) vez, y usted repite que | V | veces.

En pseudo-código:

V = {2...,n} 
U = {1} 
T = NULL 
P = array, for each v set P[v] = (1,v) 

while V != U 

    (u,v) = P[v] with v such that length P[v] is minimal 

    T = T + {(u,v)} 
    U = U + {v} 

    for each w adjacent to v 
     if length (v,w) < length P[w] then 
      P[w] = (v,w)

Fuente

2010-08-06 11:59:31

¿Puedes escribir un pequeño pseudocódigo? –

Claro. Editado mi respuesta. –

puede ordenar los bordes por el costo y luego recorrer los bordes en el orden del costo, y si esa ventaja se une a dos subgrafos distintas utilizar esa ventaja.

Tengo una implementación here. Lee el número de vértices (N), el número de bordes (M) y los bordes en orden (A, B, Costo) y luego saca los bordes. Este es el algoritmo de Kruskal.

Se puede encontrar una implementación del algoritmo de Prim con un montón, usando la misma entrada here.

Fuente

2010-08-06 13:50:25

Algoritmo MST de Prim en O (| V |^2)

Respuesta

Cuestiones relacionadas