Ciao a tutti.
In questo articolo, ho deciso di elencare le principali strutture dati utilizzate per memorizzare grafi in informatica, e parlerò anche di alcune altre strutture che in qualche modo si sono "cristallizzate" da sole.
Iniziamo. Ma non dall'inizio: penso che sappiamo già cosa sia un grafo e quali tipi ci siano (orientati, non orientati, pesati, non pesati, con archi multipli e cicli o senza).
Quindi, vediamo. Quali sono le opzioni di strutture dati per la "memorizzazione di grafi" che abbiamo.
1. Strutture di 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, e il valore di ciascun elemento a(i,j) è determinato dalla presenza o assenza di archi tra i vertici i e j (è evidente che per un grafo non orientato tale matrice sarà simmetrica, oppure possiamo concordare di memorizzare tutti i valori solo al di sopra della diagonale principale). Per i grafi non pesati, a(i,j) può essere definito come il numero di archi da i a j (se non esiste tale arco, allora a(i,j) = 0), mentre per i grafi pesati, anche – come il peso (peso totale) degli archi menzionati.
1.2 La matrice di incidenza. In questo caso, il nostro grafo è anche memorizzato in una tabella, in cui, di norma, i numeri delle righe corrispondono ai numeri dei suoi vertici, e i numeri delle colonne agli spigoli previamente numerati. Se un vertice e uno spigolo sono incidenti tra loro, viene registrato un valore diverso da zero nella cella corrispondente (per i grafi non orientati si scrive 1 in caso di incidenti tra il vertice e lo spigolo, per quelli orientati – «1», se lo spigolo «esce» dal vertice e «-1», se «entra» nel vertice (è facile ricordarlo, poiché il segno «meno» entra anche nel numero «-1»)). Per i grafi pesati, invece di 1 e -1 si può indicare il peso totale dello spigolo.
2. Strutture dati elencabili
2.1 Lista di adiacenza. Qui, apparentemente, è tutto semplice. A ciascun vertice del grafo si può, in generale, associare qualsiasi struttura elencabile (lista, vettore, array, …) in cui verranno memorizzati i numeri di tutti i vertici adiacenti. Per i grafi orientati, inseriremo in tale lista solo quei vertici in cui c'è uno spigolo «direzionato» che esce dal vertice di partenza. Per i grafi pesati, l'implementazione sarà più complessa.
2.2 Elenco dei bordi. Una struttura dati piuttosto popolare. L'elenco dei bordi, come ci suggerisce il Capitano Ovvia, rappresenta effettivamente un elenco di bordi di un grafo, ognuno dei quali è definito da un vertice iniziale, un vertice finale (per i grafi non orientati l'ordine non ha importanza, anche se per uniformità si possono utilizzare diverse regole, ad esempio, indicare i vertici in ordine crescente) e un peso (solo per i grafi pesati).
Puoi trovare maggiori dettagli (e illustrazioni) sui precedenti elenchi-matrici, ad esempio, .
2.3 Array di adiacenza. Non è una struttura molto comune. In sostanza, rappresenta una forma di "imballaggio" delle liste di adiacenza in una sola struttura enumerativa (array, vettore). I primi n (pari al numero dei vertici del grafo) elementi di tale array contengono gli indici di partenza dello stesso array, a partire dai quali sono registrati consecutivamente tutti i vertici adiacenti a quello dato.
Qui ho trovato la spiegazione più comprensibile (per me):
3. Vettore di adiacenza e Array associativo di adiacenza
È curioso notare come l'autore di queste righe, sebbene non sia un programmatore professionista, abbia comunque avuto a che fare con i grafi, e nella maggior parte dei casi con le liste degli archi. In effetti, è utile avere nel grafo diverse successioni e archi. Pertanto, per sviluppare i classici elenchi di archi, propongo di focalizzarci sul loro "sviluppo/ramificazione/modifica/mutazione", vale a dire: sul vettore di adiacenza e sull'array associativo di adiacenza.
3.1 Vettore di adiacenza
Caso (a1): grafo non pesato
Definiamo il vettore di adiacenza per un grafo non pesato come un insieme ordinato di un numero pari di interi (a[2i], a[2i+1],…, dove i è numerato a partire da 0), in cui ogni coppia di numeri a[2i], a[2i+1] rappresenta un arco del grafo tra i vertici a[2i] e a[2i+1].
Questo formato di registrazione non fornisce informazioni se il grafo è orientato (è possibile in entrambi i casi). Quando si utilizza il formato per un grafo orientato, si considera che il bordo 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 far sì che il vertice con il minor valore assegnato venga prima).
In C++, è opportuno definire il vettore di adiacenza utilizzando std::vector, da cui è stato scelto il nome di questa struttura dati.
Caso (a2): grafo non pesato, pesi dei bordi interi.
Analogamente al caso (a1), chiameremo vettore di adiacenza per un grafo pesato con pesi interi un insieme ordinato (array dinamico) di numeri (a[3i], a[3i+1], a[3i+2],…, dove i è numerato da 0), dove ogni 'tripletta' di numeri a[3i], a[3i+1], a[3i+2] definisce un bordo del grafo tra i vertici con i numeri a[3i] e a[3i+1], rispettivamente, e il valore a[3i+2] è il peso di quel bordo. Tale grafo può anche essere orientato o meno.
Caso (b): grafo non pesato, pesi dei bordi non interi.
Poiché non è possibile memorizzare elementi eterogenei in un singolo array (vettore), è possibile, ad esempio, una seguente implementazione. Il grafo è memorizzato in una 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 (una possibile implementazione in 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?
Beh, per l'autore di queste righe, per risolvere una serie di problemi, ciò è sembrato abbastanza utile. Formalmente, 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.
- In linea di principio, i vertici di un grafo possono essere contrassegnati anche con numeri negativi. Potrebbe rivelarsi utile anche un tale "sfizio".
- I grafi possono contenere più archi e più anelli, con pesi diversi (positivi, negativi, anche zero). Non ci sono limitazioni in questo caso.
- Inoltre, agli archi possono essere assegnate diverse proprietà, ma di questo si parla nel par. 4.
Tuttavia, bisogna riconoscere che questo "elenco" non prevede accesso rapido agli archi. Qui interviene l'Array associativo di adiacenza, come descritto di seguito.
3.2 Array associativo di adiacenza
Quindi, se l'accesso a un determinato arco, al suo peso e ad altre proprietà è critico per noi, e le richieste di memoria non ci consentono di utilizzare una matrice di adiacenza, pensiamo a come possiamo modificare il vettore di adiacenza per risolvere questo problema. Quindi, il punto chiave è l'arco del grafo, che può essere rappresentato come una coppia ordinata di numeri interi. A cosa somiglia? Forse è proprio una chiave in un array associativo? E se sì, perché non implementarlo? Supponiamo di avere un tale array associativo, dove a ogni chiave — coppia ordinata di numeri interi — è associato un valore, un numero intero o reale che rappresenta il peso dell'arco. In C++, è sensato implementare questa struttura sulla base del contenitore std::map (std::map<std::pair, int> o std::map<std::pair, double>), oppure std::multimap, se si prevedono più archi. Ecco fatto, abbiamo creato una struttura per memorizzare grafi che occupa meno memoria rispetto alle strutture 'matriciali', può rappresentare grafi con archi e cicli multipli e non ha nemmeno requisiti rigidi sulla non negatività degli identificativi dei nodi (non so a chi serva, ma tant'è).
4. Le strutture dati possono essere molto complesse, ma potrebbe mancare qualcosa.
È vero: nel risolvere alcuni problemi potremmo avere la necessità di attribuire determinate caratteristiche ai bordi di un grafo e, di conseguenza, di memorizzarle. Se è possibile ridurre in modo univoco queste caratteristiche a numeri interi, allora è possibile memorizzare tali "grafi con caratteristiche aggiuntive" utilizzando versioni avanzate del vettore di adiacenza e dell'array associativo di adiacenza.
Dunque, supponiamo che abbiamo un grafo non pesato, per ogni arco del quale è necessario memorizzare, ad esempio, 2 attributi aggiuntivi rappresentati da numeri interi. In questo caso, è possibile definire il suo vettore di adiacenza come un insieme ordinato non di "coppie", ma di "quattro" numeri interi (a[2i], a[2i+1], a[2i+2], a[2i+3]…), dove a[2i+2] e a[2i+3] definiranno gli attributi dell'arco corrispondente. Per un grafo con pesi interi degli archi, l'ordine, in generale, è simile (l'unica differenza sarà che gli attributi seguiranno il peso dell'arco e saranno rappresentati dagli elementi a[2i+3] e a[2i+4], e l'arco stesso sarà rappresentato non da 4, ma da 5 numeri ordinati). Per un grafo con pesi non interi, gli attributi possono essere scritti nel suo componente non pesato.
Utilizzando un array associativo di adiacenza per grafi con pesi interi, è possibile specificare come valore non solo un singolo numero, ma un array (vettore) di numeri che definisce, oltre al peso dell'arco, tutte le altre caratteristiche necessarie. Un inconveniente nel caso di pesi non interi sarebbe la necessità di specificare le caratteristiche come numeri in virgola mobile (sì, è un inconveniente, ma se tali caratteristiche non sono molte e non vengono specificate come "sottili" double, potrebbe anche andare). Quindi, in C++, gli array associativi di adiacenza estesi possono essere definiti come: std::map <std::pair , std::vector> o std::map <std::pair , std::vector, dove il primo valore nel "vettore-valore-per-chiave" sarà il peso dell'arco e le seguenti saranno le designazioni numeriche delle sue caratteristiche.
Letteratura:
Sui grafi e sugli algoritmi in generale:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmi: costruzione e analisi, 2ª edizione: Trad. dall'inglese – Mosca: Casa editrice "Williams", 2011.
2. Harari Frank. Teoria dei grafi. Mosca: Mir, 1973.
Relazione dell'autore sui vettori e sui dizionari associativi di adiacenza:
3. Chernouhov S.A. Vettore di adiacenza e dizionario associativo di adiacenza come metodi per rappresentare e memorizzare grafi / S.A. Chernouhov. Vettore di adiacenza e mappa di adiacenza come strutture dati per rappresentare un grafo // Raccolta di articoli della Conferenza scientifico-pratica internazionale "Problemi di implementazione dei risultati delle innovazioni e modi per risolverli" (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, pp. 65-69
Fonti utili su Internet sull'argomento:
4.
5.
Fonte: habr.com
