Segundo árbol de expansión de costo mínimo

Question

Estoy escribiendo un algoritmo para encontrar el segundo árbol de expansión de costo mínimo. mi idea era la siguiente:

1. Use kruskals para encontrar el MST más bajo.
2. Elimina el borde del costo más bajo del MST.
3. Ejecuta kruskals nuevamente en todo el gráfico.
4. devuelve el nuevo MST.

Mi pregunta es: ¿Funcionará? ¿Hay una mejor manera de hacer esto?

Answer 1

consideran este caso:

------100---- 
|   | 
A--1--B--3--C 
     |  | 
     |  3 
     |  | 
     2-----D 

El MST se compone de A-B-D-C (costo 6). El segundo costo mínimo es A-B-C-D (costo 7). Si elimina el límite del costo más bajo, obtendrá A-C-B-D (costo 105) en su lugar.

Así que su idea no funcionará. Aunque no tengo una idea mejor ...

Answer 2

Puede hacer esto: intente eliminar los bordes del MST, uno a la vez del gráfico, y ejecutar el MST, sacando el mínimo de él. Así que esto es similar al tuyo, excepto por iterativo:

1. Usa Kruskals para encontrar MST.
2. Para cada borde de MST: Borde
   1. Quitar del gráfico
   2. Calcular MST en MST
   3. No pierda de vista más pequeño MST
   4. Añadir borde posterior para graficar
3. retorno del el MST más pequeño.

Answer 3

Puede hacerlo en O (V). Primero calcule el MST usando Prim's algorithm (puede hacerse en O (V)).

Compute max[u, v] = the cost of the maximum cost edge on the (unique) path from u to v in the MST. Se puede hacer en O (V).

Encuentra un borde (u, v) que NO forma parte del MST que minimiza abs(max[u, v] - weight(u, v)). Se puede hacer en O (E) == O (V).

Devuelve MST' = MST - {the edge that has max[u, v] weight} + {(u, v)}, que le dará el segundo mejor MST.

Here's a link pseudocódigo y explicaciones más detalladas.

Answer 4

Aquí es un algoritmo que calcula el segundo árbol de expansión mínima en O (n^2)

1. En primer lugar encontrar el árbol de expansión mimimum (T). Tomará O (n^2) sin usar el montón.
2. Repita para cada borde e en T.= O (n^2)

3. Digamos que el borde del árbol actual es e. El borde de este árbol dividirá el árbol en dos árboles, digamos T1 y T-T1. e=(u,v) donde u está en T1 y v está en T-T1. = O (n^2)

   Repita para cada vértice v en T-T1. = O (n^2)

   Select borde e'=(u,v) para todo v en T-T1 y e' es en G (gráfico original) y es mínimo

4. calcular el peso de árbol recién formado. Digamos que W=weight(T)-weight(e)+weight(e')

5. seleccionar el que T1 que tiene un peso mínimo

Answer 5

Esto es similar a la respuesta de Larry.

Después de encontrar MST,

Para cada new_edge = no es una ventaja en el MST

1. Añadir new_edge al MST.
2. Encuentra el ciclo que se forma.
3. Encuentra el borde con el peso máximo en ciclo que no es el borde no MST que has agregado.
4. Registre el aumento de peso como W_Inc = w (new_edge) - w (max_weight_edge_in_cycle).
5. Si W_Inc < Min_W_Inc_Seen_So_Far Entonces
   • Min_W_Inc_Seen_So_Far = W_Inc
   • edge_to_add = new_edge
   • edge_to_remove = max_weight_edge_in_cycle

solución del siguiente enlace.
http://web.mit.edu/6.263/www/quiz1-f05-sol.pdf

Answer 6

Su enfoque no funcionará, ya que podría ser el caso de que mín. el borde de peso en el MST es un puente (solo un borde que conecta 2 partes del gráfico), por lo que eliminar este borde del conjunto dará como resultado 2 nuevos MST en comparación con un MST.

Answer 7

ligera edición a su algo.

Use kruskals to find lowest MST. 
    for all edges i of MST 
     Delete edge i of the MST. 
     Run kruskals again on the entire graph. 
     loss=cost new edge introduced - cost of edge i 
    return MST for which loss is minimum