Come è possibile eseguire un'operazione di vertice di aggiunta in un tempo costante per un grafico rappresentato utilizzando l'elenco di adiacenza?

1

L'aggiunta di un vertice in un grafico rappresentato utilizzando un elenco di adiacenze richiede O (1) complessità temporale in base al collegamento (operazione di grafico > adjacency list > add vertice).

Si dice che l'elenco di adiacenza detenga tutto il vertice in un array e mantiene un elenco collegato di vertici adiacenti, se vogliamo aggiungere un vertice allora dobbiamo copiare l'intero array sul nuovo array con spazio extra in modo tale che l'operazione prenderebbe O (| v |) tempo ma dicono O (1) come è possibile?

    
posta k4vin 20.09.2015 - 15:08
fonte

1 risposta

3

È possibile perché le "liste" in una rappresentazione di elenchi di adiacenze non sono necessariamente matrici raw.

In particolare, l'aggiunta di un nuovo nodo a un elenco collegato è un'operazione O (1), quindi se si crea l'elenco di adiacenze tra gli elenchi collegati, aggiungere un nuovo nodo o bordo è O (1).

Come il grafico che hai linkato indica, anche le pile e le tabelle hash hanno l'inserimento O (1) così puoi usarle anche tu, ma gli stack probabilmente renderebbero molte altre operazioni molto scomode e le tabelle hash sono solo O ( 1) date alcune forti ipotesi sulla funzione di hashing che sono difficili da giustificare, quindi di solito presumo che gli elenchi di adiacenza siano fatti da liste collegate se vogliono l'inserimento di nodi / edge a tempo costante.

Vale anche la pena notare che anche se si utilizzavano gli array, si avrebbe comunque ammortizzata la complessità a tempo costante per l'inserimento del nodo, perché il caso peggiore di O (| v |) dovrebbe essere un raro occorrenza. Non è chiaro se il grafico che hai collegato includa eventuali complessità ammortizzate.

    
risposta data 20.09.2015 - 17:15
fonte

Leggi altre domande sui tag