Ciao.
In questa nota, ho deciso di elencare le principali strutture dati utilizzate per memorizzare i grafici in informatica, e parlerò anche di un paio di altre strutture simili che in qualche modo si sono "cristallizzate" per me.
Quindi, cominciamo. Ma non dall'inizio: penso che tutti sappiamo già cos'è un grafico e cosa sono (diretto, non orientato, ponderato, non ponderato, con o senza più bordi e anelli).
Quindi andiamo. Quali opzioni abbiamo per le strutture dati per la “memorizzazione dei grafici”?
1. Strutture dati matriciali
1.1 Matrice di adiacenza. La matrice di adiacenza è una matrice in cui le intestazioni di riga e colonna corrispondono ai numeri dei vertici del grafico e il valore di ciascuno dei suoi elementi a(i,j) è determinato dalla presenza o assenza di bordi tra i vertici i e j (è chiaro che per un grafico non orientato tale matrice sarà simmetrica, oppure possiamo concordare di memorizzare tutti i valori solo sopra la diagonale principale). Per i grafici non pesati, a(i,j) può essere impostato dal numero di archi da i a j (se non esiste tale arco, allora a(i,j)= 0), e per i grafici pesati, anche dal peso (peso totale) dei bordi menzionati.
1.2 Matrice di incidenza. In questo caso, il nostro grafico è anche memorizzato in una tabella in cui, di regola, i numeri delle righe corrispondono ai numeri dei suoi vertici e i numeri delle colonne corrispondono ai bordi prenumerati. Se un vertice e un bordo sono incidenti tra loro, allora viene scritto un valore diverso da zero nella cella corrispondente (per grafici non orientati, viene scritto 1 se il vertice e il bordo sono incidenti, per grafici orientati - "1" se il bordo “esce” dal vertice e “-1” se “include” in esso (è abbastanza facile da ricordare, perché anche il segno “meno” sembra essere “incluso” nel numero “-1”). Per i grafici ponderati, ancora una volta, invece di 1 e -1, è possibile specificare il peso totale del bordo.
2. Strutture dati di enumerazione
2.1 Elenco delle adiacenze. Bene, qui tutto sembra essere semplice. Ogni vertice del grafico può, in generale, essere associato a qualsiasi struttura di enumerazione (lista, vettore, array, ...), che memorizzerà i numeri di tutti i vertici adiacenti a quello dato. Per i grafi diretti, aggiungeremo a tale elenco solo quei vertici verso i quali esiste un bordo “diretto” da un vertice della caratteristica. Per i grafici pesati l'implementazione sarà più complessa.
2.2 Elenco delle costole. Una struttura dati piuttosto popolare. L'elenco degli archi, come ci dice Captain Obviousness, è in realtà un elenco di archi del grafo, ognuno dei quali è specificato dal vertice iniziale, dal vertice finale (per i grafi non orientati l'ordine qui non è importante, sebbene per l'unificazione si possa utilizzare varie regole, ad esempio specificando i vertici in ordine crescente) e il peso (solo per i grafici pesati).
Puoi esaminare gli elenchi di matrici sopra elencati in modo più dettagliato (e con illustrazioni), ad esempio, .
2.3 Array di adiacenza. Non la struttura più comune. Fondamentalmente, è una forma di “impacchettamento” di elenchi di adiacenza in un'unica struttura di enumerazione (array, vettore). I primi n (in base al numero di vertici del grafico) elementi di un tale array contengono gli indici iniziali dello stesso array, a partire dal quale vengono scritti in una riga tutti i vertici adiacenti a quello dato.
Qui ho trovato la spiegazione più comprensibile (per me):
3. Vettore di adiacenza e matrice di adiacenza associativa
Si è scoperto che l'autore di queste righe, non essendo un programmatore professionista, ma che si occupava periodicamente di grafici, molto spesso si occupava di elenchi di bordi. In effetti, è conveniente se il grafico ha più anelli e spigoli. E così, nello sviluppo delle classiche liste di archi, propongo di prestare attenzione al loro “sviluppo/ramo/modifica/mutazione”, ovvero: il vettore di adiacenza e l'array associativo di adiacenza.
3.1 Vettore di adiacenza
Caso (a1): grafico non ponderato
Chiameremo vettore di adiacenza per un grafo non pesato un insieme ordinato di un numero pari di interi (a[2i], a[2i+1],..., dove i è numerato c 0), in cui ciascuna coppia di numeri è a[2i], a[2i+1] specifica un bordo del grafico tra i vertici a[2i] e a[2i+1], rispettivamente.
Questo formato di registrazione non contiene informazioni sull'orientamento del grafico (entrambe le opzioni sono possibili). Quando si utilizza il formato digramma, il bordo è considerato diretto da a[2i] a a[2i+1]. Qui e sotto: per i grafi non orientati, se necessario, si possono applicare requisiti relativi all'ordine di registrazione dei vertici (ad esempio, che il vertice con il valore inferiore del numero assegnato venga prima).
In C++ è consigliabile specificare un vettore di adiacenza utilizzando std::vettore, da cui il nome di questa struttura dati.
Caso (a2): grafico non ponderato, i pesi degli archi sono interi
Per analogia con il caso (a1), chiamiamo vettore di adiacenza per un grafo pesato con archi interi che pesa un insieme ordinato (array dinamico) di numeri (a[3i], a[3i+1], a[3i+2], ..., dove i è numerato c 0), dove ciascuna “tripletta” di numeri a[3i], a[3i+1], a[3i+2] specifica un bordo del grafico tra i vertici numerati a[3i] e a[3i+1], rispettivamente, e il valore a[3i+2] è il peso di questo bordo. Tale grafico può anche essere orientato o meno.
Caso (b): grafico non pesato, pesi degli archi non interi
Poiché ad esempio non è possibile memorizzare elementi eterogenei in un array (vettore), è possibile la seguente implementazione. Il grafico è memorizzato in una coppia di vettori, in cui il primo vettore è il vettore di adiacenza del grafico senza specificare i pesi, e il secondo vettore contiene i pesi corrispondenti (possibile implementazione per C++: std::pair ). Pertanto, per un bordo definito da una coppia di vertici sotto gli indici 2i, 2i+1 del primo vettore, il peso sarà uguale all'elemento sotto l'indice i del secondo vettore.
Ebbene, perché è necessario?
Ebbene, l'autore di queste righe lo ha trovato piuttosto utile per risolvere una serie di problemi. Ebbene, dal punto di vista formale i vantaggi saranno i seguenti:
- Il vettore di adiacenza, come qualsiasi altra struttura “enumerativa”, è abbastanza compatto, occupa meno memoria della matrice di adiacenza (per grafi sparsi) ed è relativamente facile da implementare.
- I vertici del grafico, in linea di principio, possono essere contrassegnati anche con numeri negativi. E se fosse necessaria una simile “perversione”?
- I grafici possono contenere più archi e più cicli, con pesi diversi (positivo, negativo e persino zero). Non ci sono restrizioni qui.
- Puoi anche assegnare proprietà diverse ai bordi, ma per ulteriori informazioni vedere la sezione 4.
Bisogna però ammettere che questa “lista” non implica un accesso rapido al bordo. E qui viene in soccorso l'array di adiacenza associativa, di cui parleremo di seguito.
3.2 Matrice di adiacenza associativa
Quindi, se l'accesso a un bordo specifico, al suo peso e ad altre proprietà è fondamentale per noi e i requisiti di memoria non ci consentono di utilizzare la matrice di adiacenza, allora pensiamo a come possiamo modificare il vettore di adiacenza per risolvere questo problema. Quindi, la chiave è un bordo del grafico, che può essere specificato come una coppia ordinata di numeri interi. Cosa sembra questo? Non è una chiave in un array associativo? E, se sì, perché non lo implementiamo? Prendiamo un array associativo in cui ogni chiave - una coppia ordinata di numeri interi - sarà associata a un valore - un numero intero o reale che specifica il peso dello spigolo. In C++ è consigliabile implementare questa struttura in base al contenitore std::map (std::map , int> o std::map , double>) o std::multimap se sono previsti più bordi. Bene, abbiamo una struttura per memorizzare i grafici che occupa meno memoria delle strutture a "matrice", può definire grafici con più cicli e archi e non ha nemmeno requisiti rigorosi per la non negatività dei numeri dei vertici (non lo so chi ne ha bisogno, ma comunque).
4. Le strutture dati sono piene, ma manca qualcosa
Ed è vero: quando risolviamo una serie di problemi, potremmo dover assegnare alcune caratteristiche ai bordi del grafico e, di conseguenza, memorizzarle. Se è possibile ridurre in modo inequivocabile queste caratteristiche a numeri interi, allora è possibile memorizzare tali "grafici con caratteristiche aggiuntive" utilizzando versioni estese del vettore di adiacenza e dell'array di adiacenza associativo.
Quindi, prendiamo un grafico non ponderato, per ciascun bordo del quale è necessario memorizzare, ad esempio, 2 caratteristiche aggiuntive specificate da numeri interi. In questo caso è possibile definire il suo vettore di adiacenza come un insieme ordinato non di “coppie”, ma di “quartetti” di interi (a[2i], a[2i+1], a[2i+2], a [2i+3]…), dove a[2i+2] e a[2i+3] determineranno le caratteristiche del bordo corrispondente. Per un grafo con pesi interi degli spigoli, l'ordine è generalmente simile (l'unica differenza sarà che gli attributi seguiranno il peso dello spigolo e saranno specificati dagli elementi a[2i+3] e a[2i+4] , e sul bordo stesso verranno specificati non 4, ma 5 numeri ordinati). E per un grafico con pesi degli archi non interi, le caratteristiche possono essere scritte nella sua componente non ponderata.
Quando si utilizza un array di adiacenza associativo per grafici con pesi degli spigoli interi, è possibile specificare come valore non un singolo numero, ma un array (vettore) di numeri che specificano, oltre al peso di un spigolo, tutti gli altri suoi valori necessari caratteristiche. Allo stesso tempo, un inconveniente nel caso di pesi non interi sarà la necessità di specificare un segno con un numero in virgola mobile (sì, questo è un inconveniente, ma se non ci sono così tanti segni simili, e se non lo fai non impostarli in modo troppo "difficile" doppio, altrimenti potrebbe non essere nulla). Ciò significa che in C++ gli array di adiacenza associativa estesa possono essere definiti come segue: std::map , std::vettore> o std::map , std::vettore, in cui il primo valore nel "vettore-valore-chiave" sarà il peso del bordo, e quindi si troveranno le designazioni numeriche delle sue caratteristiche.
letteratura:
Informazioni su grafici e algoritmi in generale:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmi: costruzione e analisi, 2a edizione: Trans. dall'inglese – M.: Casa editrice Williams, 2011.
2. Harari Frank. Teoria dei grafi. M.: Mir, 1973.
Rapporto dell'autore su questi stessi vettori e array associativi di adiacenze:
3. Chernoukhov S.A. Vettore di adiacenza e array di adiacenza associativa come modi per rappresentare e memorizzare grafici / SA Chernouhov. Vettore di adiacenza e mappa di adiacenza come strutture dati per rappresentare un grafico // Raccolta di articoli della conferenza scientifica e pratica internazionale "Problemi di implementazione dei risultati di sviluppi innovativi e modi per risolverli" (Saratov, 14.09.2019 settembre 2019). – Sterlitamak: AMI, 65, pag. 69-XNUMX
Fonti online utili sull'argomento:
4.
5.
Fonte: habr.com