Ciao a tutti.
In questo articolo ho deciso di elencare le principali strutture dati utilizzate per la memorizzazione dei grafi in informatica e parlerò anche di un paio di altre strutture che in qualche modo si sono «cristallizzate» da sole.
Iniziamo. Ma non dall'inizio: penso che sappiamo tutti cos'è un grafo e quali sono le sue varianti (orientati, non orientati, pesati, non pesati, con archi multipli e anelli o senza di essi).
Quindi, andiamo. Quali sono le opzioni di strutture dati per la «memorizzazione dei grafi» che abbiamo.
1. Strutture dati matriciali
1.1 Matrice di adiacenza. La matrice di adiacenza è una matrice in cui le intestazioni delle righe e delle colonne corrispondono ai numeri dei vertici del grafo, mentre il valore di ciascun elemento a(i,j) è determinato dalla presenza o assenza di archi tra i vertici i e j (è chiaro che per un grafo non orientato tale matrice sarà simmetrica oppure possiamo concordare che memorizziamo solo i valori sopra la diagonale principale). Per i grafi non pesati, a(i,j) può essere definito dal numero di archi da i a j (se non esiste tale arco, a(i,j)= 0), mentre per i grafi pesati anche dal peso (peso totale) degli archi menzionati.
1.2 Matrice di incidenza. In questo caso, il nostro grafo è anch'esso memorizzato in una tabella, in cui, di norma, i numeri delle righe corrispondono ai numeri dei suoi vertici e i numeri delle colonne agli archi numerati in precedenza. Se un vertice e un arco sono incidenti tra loro, nella cella corrispondente viene registrato un valore diverso da zero (per i grafi non orientati si registra 1 in caso di incidenza tra il vertice e l'arco, per i grafi orientati si registra «1» se l'arco «esce» dal vertice e «-1» se «entra» in esso (è facile da ricordare, poiché il segno «meno» appare anch'esso all'interno del numero «-1»)). Per i grafi pesati, al posto di 1 e -1 si può indicare nuovamente il peso totale dell'arco.
2. Strutture dati enumerative
2.1 Lista di adiacenza. Beh, qui sembra tutto semplice. A ogni vertice del grafo si può, in linea di massima, associare qualsiasi struttura enumerativa (lista, vettore, array, …) in cui saranno memorizzati i numeri di tutti i vertici adiacenti a quello dato. Per i grafi orientati, inseriremo in tale lista solo quei vertici a cui c'è un arco 'direzionato' dal vertice distintivo. Per i grafi pesati l'implementazione sarà più complessa.
2.2 Lista degli archi. Una struttura dati abbastanza popolare. La lista degli archi, come ci suggerisce il Capitano Ovvietà, rappresenta effettivamente una lista degli archi del grafo, ognuno dei quali è definito da un vertice iniziale, un vertice finale (per i grafi non orientati, qui l'ordine non è importante, anche se per uniformità si possono usare varie regole, ad esempio, indicare i vertici in ordine crescente) e un peso (solo per i grafi pesati).
Puoi dare un'occhiata più nel dettaglio (e con illustrazioni) delle liste-matrici sopra menzionate, ad esempio, .
2.3 Array di adiacenza. Non è una struttura che si incontra frequentemente. In sostanza, rappresenta una forma di 'imballaggio' delle liste di adiacenza in una singola struttura enumerativa (array, vettore). I primi n (in base al numero di vertici del grafo) elementi di questo array contengono gli indici di partenza del medesimo array, a partire dai quali sono scritti consecutivamente tutti i vertici adiacenti.
Ecco qui ho trovato la spiegazione più chiara (per me):
3. Vettore di adiacenza e Array associativo di adiacenza
È andata così, che l'autore di queste righe, non essendo un programmatore professionista, ma avendo comunque a che fare con i grafi di tanto in tanto, ha frequentemente utilizzato liste di archi. Infatti, è comodo, quando ci sono più cicli e archi in un grafo. E così, in funzione delle classiche liste di archi, propongo di prestare attenzione anche al loro 'sviluppo/ramo/modifica/mutazione', ovvero: vettore di adiacenza e array associativo di adiacenza.
3.1 Vettore di adiacenza
Caso (a1): grafo non pesato
Definiremo vettore di adiacenza per un grafo non pesato un insieme ordinato di un numero pari di interi (a[2i], a[2i+1],…, dove i è indicizzato a partire da 0), in cui ogni coppia di numeri a[2i], a[2i+1] definisce un arco del grafo tra i vertici a[2i] e a[2i+1] rispettivamente.
Questo formato di registrazione non fornisce informazioni su se il grafo sia orientato (sono possibili entrambe le opzioni). Quando si utilizza il formato per un grafo orientato, si considera che un arco sia diretto da a[2i] ad a[2i+1]. Qui e in seguito: per i grafi non orientati, se necessario, possono essere applicati requisiti per l'ordine di registrazione dei vertici (ad esempio, per iniziare con il vertice con il valore numerico assegnato più basso).
In C++, è opportuno definire il vettore di adiacenza utilizzando std::vector, da qui il nome scelto per questa struttura dati.
Caso (a2): grafo non pesato, pesi degli archi interi.
Analogamente al caso (a1), chiameremo vettore di adiacenza per un grafo pesato con pesi degli archi interi un insieme ordinato (array dinamico) di numeri (a[3i], a[3i+1], a[3i+2],…, dove i è numerato da 0), in cui ogni "triplet" di numeri a[3i], a[3i+1], a[3i+2] definisce un arco del grafo tra i vertici contrassegnati con i numeri a[3i] e a[3i+1] rispettivamente, mentre il valore a[3i+2] rappresenta il peso di questo arco. Tale grafo può essere sia orientato che non orientato.
Caso (b): grafo non pesato, pesi degli archi non interi.
Poiché non è possibile memorizzare elementi eterogenei in un unico array (vettore), è possibile, ad esempio, la seguente implementazione. Il grafo è memorizzato in coppia di vettori, dove il primo vettore è il vettore di adiacenza del grafo senza indicazione dei pesi, e il secondo vettore contiene i pesi corrispondenti (possibile implementazione per C++: std::pair). Pertanto, per un arco definito da una coppia di vertici agli indici 2i, 2i+1 del primo vettore, il peso sarà uguale all'elemento all'indice i del secondo vettore.
Ma a cosa serve tutto ciò?
Beh, per l'autore di queste righe, per risolvere una serie di problemi, è sembrato abbastanza utile. E dal punto di vista formale, ci saranno i seguenti vantaggi:
- Il vettore di adiacenza, come qualsiasi altra struttura "enumerativa", è abbastanza compatto, occupa meno memoria rispetto alla matrice di adiacenza (per grafi sparsi), ed è relativamente semplice da implementare.
- I vertici del grafo, in linea di principio, possono essere contrassegnati anche con numeri negativi. Potrebbe darsi che sia necessario un simile "stravizio".
- I grafi possono contenere archi multipli e cicli multipli, anche con pesi diversi (positivi, negativi, anche zero). Non ci sono limitazioni in questo.
- Inoltre, è possibile assegnare diverse proprietà agli archi - ma a questo si fa riferimento nel punto 4.
Tuttavia, va detto che questo 'elenco' non prevede un accesso rapido all'arco. E qui interviene l'Array associativo di adiacenza, come spiegato di seguito.
3.2 Array associativo di adiacenza
Quindi, se l'accesso a un arco specifico, al suo peso e ad altre proprietà è critico per noi, e le limitazioni di memoria non ci permettono di utilizzare una matrice di adiacenza, consideriamo come possiamo modificare il vettore di adiacenza per risolvere questo problema. Quindi, la chiave è l'arco del grafo, che può essere rappresentato come una coppia ordinata di numeri interi. A cosa assomiglia? Non è forse come una chiave in un array associativo? E se fosse così, perché non implementarlo? Supponiamo di avere un tale array associativo, dove a ogni chiave - coppia ordinata di numeri interi - viene associato un valore - un numero intero o reale che definisce il peso dell'arco. In C++, è opportuno implementare questa struttura basandosi sul contenitore std::map (std::map <std::pair , int> o std::map <std::pair , double>), o std::multimap, se si prevede di avere archi multipli. Ecco, abbiamo ottenuto una struttura per memorizzare grafi che occupa meno memoria rispetto alle strutture 'matriciali', può definire grafi con più anelli e archi e non ha nemmeno rigide restrizioni sull'interezza dei numeri dei vertici (non so a chi serva, ma ci sono comunque).
4. Strutture di dati: qualcosa sembra mancare
E in effetti: nella risoluzione di diversi problemi, potrebbe sorgere la necessità di assegnare alcuni attributi agli archi del grafo e, di conseguenza, di memorizzarli. Se è possibile ridurre in modo univoco questi attributi a numeri interi, allora si possono memorizzare tali 'grafi con attributi aggiuntivi' utilizzando versioni avanzate del vettore di adiacenza e dell'array associativo di adiacenza.
Dunque, supponiamo di avere un grafo non pesato, nel quale per ogni arco è necessario memorizzare, ad esempio, 2 caratteristiche aggiuntive, definite da numeri interi. In questo caso, è possibile definire il suo vettore di adiacenza come un insieme ordinato non di "coppie", ma di "quarità" di numeri interi (a[2i], a[2i+1], a[2i+2], a[2i+3]…), dove a[2i+2] e a[2i+3] definiranno le caratteristiche dell'arco corrispondente. Per un grafo con pesi interi degli archi, l'ordine, in generale, è simile (l'unica differenza sarà che le caratteristiche seguiranno dopo il peso dell'arco e saranno definite dagli elementi a[2i+3] e a[2i+4], e l'arco stesso sarà definito non da 4, ma da 5 numeri ordinati). E per un grafo con pesi non interi degli archi, le caratteristiche possono essere scritte nel suo componente non pesato.
Utilizzando un array associativo di adiacenza per grafi con pesi interi degli archi, è possibile definire come valore non un singolo numero, ma un array (vettore) di numeri che definiscono, oltre al peso dell'arco, tutte le altre caratteristiche necessarie. Tuttavia, un inconveniente nel caso di pesi non interi sarà la necessità di definire una caratteristica come un numero in virgola mobile (sì, è un inconveniente, ma se tali caratteristiche non sono molte e se non vengono definite in modo troppo "astuto" come double, potrebbe non essere un problema). Pertanto, in C++, gli array associativi di adiacenza possono essere definiti come segue: std::map <std::pair , std::vector> oppure std::map <std::pair , std::vector>, dove il primo valore nel "vettore-valore-per-chiave" sarà il peso dell'arco e le sue caratteristiche numeriche seguiranno.
Letteratura:
Sui grafi e sugli algoritmi in generale:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmi: progettazione e analisi, 2ª edizione: Trad. dall'inglese – Mosca: Editoriale "Williams", 2011.
2. Harari, Frank. Teoria dei grafi. Mosca: Mir, 1973.
Relazione dell'autore su questo stesso vettore e sull'array associativo di adiacenza:
3. Chernouhov S.A. Vettore di adiacenza e mappa di adiacenza come strutture dati per rappresentare un grafo // Raccolta di articoli della Conferenza scientifico-pratica internazionale «Problemi di attuazione dei risultati dello sviluppo innovativo e modi per risolverli» (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, pp. 65-69
Fonti Internet utili sull'argomento:
4.
5.
Fonte: habr.com
