Implementazione di grafici sparsi e prestazioni in C++

Question

Attualmente sto lavorando a una struttura di dati del grafico diretto in C++ (nessun Boost GL per questo progetto). L'applicazione principale identificherà i componenti e i sink collegati. Ci si aspetta che i grafici siano sparsi (limite superiore di E ~ 4 V sui bordi numerici) e saranno tutti di peso uniforme. Sto cercando di decidere tra la lista di adiacenze, la lista di incidenza o forse qualche altra rappresentazione che non ho ancora sentito (matrice matriciale non un'opzione bc di sparsità). Il collo di bottiglia sarà probabilmente lo spazio complessivo e la velocità di inizializzazione del grafico: i grafici saranno inizializzati da array potenzialmente enormi in modo tale che ogni elemento dell'array finirà per essere un vertice con un bordo diretto a uno dei suoi elementi vicini. Per ottenere i bordi per ogni vertice, è necessario confrontare prima tutti gli elementi adiacenti.

Le mie domande sono: (1) Quale rappresentazione è in genere più veloce da inizializzare e anche veloce per BFS traversal, (2) Quali algoritmi (diversi da BFS vaniglia) esistono per trovare i componenti connessi? So che è O (V + E) che usa BFS (che è ottimale, penso) ma sono preoccupato per la dimensione della coda intermedia mentre la larghezza del grafico cresce esponenzialmente con l'altezza.

Non ho troppa esperienza con le implementazioni di grafici, quindi sarei grato per eventuali suggerimenti.

Answer 1

consideri un layout come segue:

Una lista di adiacenza può essere implementato come una serie di [NX4] (n essendo 3 in questo caso, e 4 perché lei sta dicendo che 4 è il numero massimo di lati nel caso) nel seguente forma:

2 3 0 0 
3 0 0 0 
0 0 0 0 

la rappresentazione precedente presuppone che il numero di vertici sono ordinati cui primo indice nella matrice è data da (v-1).

L'elenco di incidenze, d'altra parte, richiede la definizione di un elenco di vertici, un elenco di bordi e elementi di connessione tra (incidence list - graph).

Entrambi sono buoni in termini di utilizzo dello spazio rispetto a una matrice di adiacenza poiché il grafico è molto scarso, come hai affermato.

Il mio suggerimento sarebbe quello di andare con la lista di adiacenza, che è possibile inizializzare come una matrice contigua [Nx4] nella memoria (dato che stai dicendo che avrai al massimo 4 spigoli per un vertice). Questa rappresentazione sarà più veloce da inizializzare. (Inoltre, questa rappresentazione avrà prestazioni migliori in termini di efficienza della cache)

Tuttavia, se si prevede che le dimensioni del grafico cambino dinamicamente e frequentemente, gli elenchi di incidenza potrebbero essere migliori poiché sono generalmente implementati come elenchi che sono spazi non contigui (vedi il link sopra). La de-allocazione e l'allocazione dell'array adiacente potrebbero non essere desiderabili in quel caso.

Answer 2

Il modo più efficiente per implementare un grafico per i propri scopi è probabilmente una combinazione di un elenco di adiacenze per ciascun vertice e inoltre una struttura di hashing che associa coppie di vertici ai bordi, se esistenti. Ciò richiederà lo spazio O (| V | + | E |) per l'elenco di adiacenza, O (| E |) per la struttura di hashing e fornirà il previsto O (1) containsEdge(vertex v, vertex w), insertEdge(vertex v, vertex w) e removeEdge(vertex v, vertex w) utilizzando la mappatura per ottenere i puntatori necessari per modificare rapidamente gli elenchi di adiacenza dei vertici.