Componenti connesse del grafo non orientato

Naviga le tue risposte
1

Supponiamo di avere un grafo non orientato G con vertici v1 ... vn e spigoli. In questo momento è nella rappresentazione della lista di adiacenza.

Per ogni momento ho come input alcuni sottoinsiemi di vertici che sono "attivi" in questo momento. E ho bisogno di trovare tutti i componenti collegati in questo sottoinsieme di vertici per quel momento.

In questo momento l'ho implementato utilizzando la struttura di dati union-find come questa: 

initialize sets for every active vertex so that every vertex has itself as "representative" (also called "parent")

for every active vertex v
   for all neighbours of v in G v_neighbour
      if v_neighbour is active
          union set of v and set of v_neighbour

Dovrebbe funzionare bene, ma voglio sapere se esiste un approccio più ottimale? E qual è il tempo di esecuzione di tale algoritmo? O (N * M)?

    
posta user1685095 21.02.2015 - 12:19
fonte

1 risposta

1

La risposta corretta in pratica può dipendere dalla proporzione approssimativa dei vertici che sono attivi. Se la maggior parte dei vertici sono attivi, modificherei la struttura del grafo eliminando tutti i collegamenti ai vertici inattivi (banale nella forma della matrice di adiacenza, molto parallelizzabile nella forma dell'elenco di adiacenza) e quindi eseguirò un algoritmo standard con componenti debolmente connessi (che dovrebbe essere O) (V + E)). Se il numero di vertici attivi è molto piccolo, la mutilazione del grafico potrebbe non valerne la pena, e solo l'espansione dai vertici attivi come suggerito potrebbe essere migliore.

Come sempre, le nostre intuizioni su queste cose dovrebbero essere verificate sperimentalmente se le prestazioni sono un problema chiave.

    
risposta data 23.02.2015 - 20:26
fonte

Leggi altre domande sui tag

Usando sourcetree / bitbucket come posso gestire più progetti usando una base di codice comune? Quale livello genera comandi per servizi dipendenti?