Aggiungi un nuovo spigolo al grafico e trova il nuovo spanning tree in O (n)

Supponiamo di avere lo spanning tree minimo T di un dato grafo G (con n vertici e m bordi) e un nuovo spigolo e = (u, v) di peso w che aggiungeremo a G. Fornire un algoritmo efficiente per trovare l'albero di copertura minimo del grafico G + e. L'algoritmo deve essere eseguito in tempo O (n) per ricevere il credito completo.Aggiungi un nuovo spigolo al grafico e trova il nuovo spanning tree in O (n)

Inizio Prim o Kruskal ALG da u o v fino a raggiungere un frammento del percorso dell'albero data spanning? Sembra che la nuova spanning tree non cambierà molto da un nuovo edge.

fonte

2011-01-26 yetanothercoder

poiché questo è un problema compiti a casa, si può spiegare più precisamente quello che vuoi aiuto? Questo è un grosso problema, ma non ti daremo la risposta. – templatetypedef

Determina il percorso tra i punti finali del nuovo spigolo in G. Se il bordo della lunghezza massima in quel percorso è maggiore di quello del nuovo spigolo, sostituirlo con il nuovo spigolo. Questo funziona nel tempo O (N).

Fonte: Trail Maintenance IOI 2003

fonte

2011-01-26 20:22:48 marcog

Risposta perfetta per una domanda non a casa. Ma è una domanda per i compiti, quindi -1. –

+16

@j_random_hacker - Alcune persone sono curiose di sapere perché hai downvoted: vedi [questa domanda su Meta] (http://meta.stackexchange.com/questions/76694). Cosa dovrebbe dire Marcog per rendere questa una risposta migliore a una domanda a casa? – ChrisW

Wow! Non mi aspettavo di creare così tante polemiche. Grazie a @ChrisW per il puntatore. Cercherò di spiegare la mia posizione su quella domanda Meta (che credo sia un ottimo esempio di una domanda Meta, BTW). –

Aggiungi un nuovo spigolo al grafico e trova il nuovo spanning tree in O (n)

risposta

Problemi correlati