Aggiornamento spanning tree minimo con modifica del bordo

Question

Un grafico (bordi di peso positivo) con un MST Se qualche spigolo, e viene modificato in un nuovo valore, qual è il modo migliore per aggiornare l'MST senza rifarlo completamente. Penso che questo possa essere fatto in tempo lineare. Inoltre, sembra che avrei bisogno di un algoritmo diverso basato sul fatto che 1) e sia già una parte del MST e 2) se il nuovo bordo, e sia più grande o più piccolo dell'originale

Answer 1

My O (n) soluzione si basa sul presupposto, che prima di iniziare a modificare i bordi, dovresti trovare MST (non è dato con il grafico). Per fare ciò, è possibile utilizzare l'algoritmo di Kruskal che funziona in O (n log n), e come effetto collaterale produce l'elenco ordinato dei bordi. Il suo costo è dominato dall'ordinamento, quindi quando modifichi il peso di un bordo, puoi eliminarlo dall'elenco ordinato in O (log n), e reinserirlo con un nuovo valore, anche in O (log n), e infine chiamare Kruskal di nuovo l'algoritmo, che ora viene eseguito in tempo lineare perché i bordi sono ordinati.

Questa è una soluzione lineare come richiesto, ma sembra che possa essere eseguita più velocemente.

Answer 2

ci sono 4 casi:

1. bordo è a MST e valore decrescente di bordo:
   MST attuale è ancora MST

2. Edge non è in MST e diminuendo valore del bordo:
   Aggiungere questo margine all'MST. Ora hai esattamente 1 ciclo.
   In base a cycle property in MST è necessario trovare e rimuovere bordo con il valore più alto che si trova su quel ciclo. Puoi farlo usando dfs o bfs. Complessità O (n).

3. Edge è in MST e aumentando il suo valore di bordo:
   Inserisci questa bordo da MST. Ora hai 2 componenti collegati che dovrebbero essere collegati. Puoi calcolare entrambi i componenti in O (n) (bfs o dfs). Hai bisogno di trovare il bordo con il più piccolo valore che collega questi componenti. Iterare i bordi in ordine crescente in base al loro valore. Complessità O (n).

4. Edge non è in MST e aumentando il suo valore di bordo:
   MST attuale è ancora MST