Cos'è la struttura dei dati del grafico?
UN Grafico è una struttura dati non lineare costituita da vertici e spigoli. I vertici sono talvolta indicati anche come nodi e gli spigoli sono linee o archi che collegano due nodi qualsiasi nel grafico. Più formalmente un grafico è composto da un insieme di vertici( IN ) e un insieme di bordi( E ). Il grafico è indicato con SOL(V, E) .
Rappresentazioni del grafico
Ecco i due modi più comuni per rappresentare un grafico:
- Matrice di adiacenza
- Elenco delle adiacenze
Matrice di adiacenza
Una matrice di adiacenza è un modo di rappresentare un grafico come una matrice di valori booleani (0 e 1).
Supponiamo che ci siano N vertici nel grafico Quindi, crea una matrice 2D adjMat[n][n] avente dimensione n x n.
- Se c'è un bordo dal vertice io A J , segno adjMat[i][j] COME 1 .
- Se non c'è bordo dal vertice io A J , segno adjMat[i][j] COME 0 .
Rappresentazione del grafico non orientato nella matrice di adiacenza:
La figura seguente mostra un grafico non orientato. Inizialmente, l'intera Matrix viene inizializzata su 0 . Se c'è un confine dalla sorgente alla destinazione, lo inseriamo 1 in entrambi i casi ( adjMat[destinazione] E adjMat [ destinazione]) perché possiamo andare in entrambe le direzioni.
Grafico non orientato alla matrice di adiacenza
Rappresentazione del grafico diretto nella matrice di adiacenza:
La figura seguente mostra un grafico diretto. Inizialmente, l'intera Matrix viene inizializzata su 0 . Se c'è un confine dalla sorgente alla destinazione, lo inseriamo 1 per quel particolare adjMat[destinazione] .
Grafico diretto alla matrice di adiacenza
Elenco delle adiacenze
Un array di elenchi viene utilizzato per memorizzare i bordi tra due vertici. La dimensione dell'array è uguale al numero di vertici (cioè n) . Ogni indice in questo array rappresenta un vertice specifico nel grafico. La voce nell'indice i dell'array contiene una lista concatenata contenente i vertici adiacenti al vertice io .
Supponiamo che ci siano N vertici nel grafico Quindi, crea un matrice di elenco di dimensione N COME adjLista[n].
- adjList[0] avrà tutti i nodi che sono collegati (vicini) al vertice 0 .
- adjList[1] avrà tutti i nodi che sono collegati (vicini) al vertice 1 e così via.
Rappresentazione del grafico non orientato alla lista delle adiacenze:
Il grafico non orientato sottostante ha 3 vertici. Verrà quindi creato un array di liste di dimensione 3, dove ogni indice rappresenta i vertici. Ora, il vertice 0 ha due vicini (cioè 1 e 2). Quindi, inserisci i vertici 1 e 2 negli indici 0 dell'array. Allo stesso modo, per il vertice 1, ha due vicini (cioè 2 e 0). Quindi, inserisci i vertici 2 e 0 negli indici 1 dell'array. Allo stesso modo, per il vertice 2, inserisci i suoi vicini nell'array della lista.
Grafico non orientato alla lista delle adiacenze
Rappresentazione del grafico diretto alla lista di adiacenze:
Il grafico diretto di seguito ha 3 vertici. Verrà quindi creato un array di liste di dimensione 3, dove ogni indice rappresenta i vertici. Ora, il vertice 0 non ha vicini. Per il vertice 1, ha due vicini (cioè 0 e 2). Quindi, inserisci i vertici 0 e 2 negli indici 1 dell'array. Allo stesso modo, per il vertice 2, inserisci i suoi vicini nell'array della lista.
Grafico diretto alla lista di adiacenze