Elenco di adiacenza in C ++
- Elenco di adiacenza
- Matrix di adiacenza
- Una matrice di incidenza
L'argomento principale di questo articolo sarà l'elenco di adiacenza. Proviamo prima a capire cosa sia veramente un grafico prima di entrare per capire meglio questa idea.
Cos'è un grafico?
Un grafico ha un numero fisso di nodi o vertici. E ogni nodo è collegato da una linea, che chiamiamo un bordo. Il bordo è per la comunicazione tra due vertici o nodi. Ad esempio, nel grafico sopra, vediamo sei vertici o nodi (0, 1, 2, 3, 4 e 5). Dal vertice o dal nodo 0, possiamo facilmente passare al vertice 1 e 3 perché esiste una connessione diretta tra di loro. Ma non esiste una connessione diretta tra vertice o nodo 0 e 4.
I grafici sono utilizzati in molte applicazioni di vita reale per risolvere i problemi di rete. Ad esempio, su Facebook, il profilo dell'utente è un nodo o un vertice e gli amici dell'utente nell'elenco sono ulteriori nodi o vertici diversi che hanno connessioni dirette tra di loro.
Tipi di grafici
Esistono principalmente due tipi di grafici, grafici non diretti e grafici diretti, entrambi sono descritti nelle sezioni successive:
Grafico non diretto
Il grafico non diretto è molto famoso perché è un grafico bidirezionale. Ad esempio, di seguito è un esempio di un grafico non indirizzato:
Grafico non diretto
Nel grafico non diretto, possiamo spostarci su qualsiasi vertice. Ad esempio, se esiste una connessione tra i nodi A e B, allora possiamo anche passare da B a A.
Grafico diretto
In un grafico diretto, i bordi hanno bordi di direzione. Quindi questi bordi della freccia ci diranno come possiamo muoverci nel grafico da un vertice a un altro vertice, ma solo in alcune condizioni. Ad esempio, se c'è un bordo diretto tra i nodi A e B, allora possiamo passare rapidamente dal vertice A a B ma non tornando da B a A se non c'è un bordo diretto da B a A.
Grafico diretto
Elenco di adiacenza
L'elenco di adiacenza è un elenco di array in cui la dimensione dell'array è uguale al numero di nodi presenti nel grafico. E ogni nodo ha anche un sotto-array che rappresenta la sua connettività ad altri nodi o vertici. Discuteremo gli elenchi di adiacenza di entrambi i tipi di grafici (non diretti e diretti).
Elenco di adiacenza grafico non diretto
Nel grafico non indirizzato sopra, possiamo vedere sei vertici (0, 1, 2, 3, 4, 5). Quindi, abbiamo una serie di sei vertici. E ogni ulteriore vertice individuale ha il proprio elenco collegato o elenco di adiacenza, come mostrato nell'elenco di adiacenza precedente. Possiamo vedere che Vertex 0 punti su Vertex 4 e Vertex 3.
Ma, come abbiamo spiegato in precedenza, un grafico non diretto può muoversi in entrambe le direzioni. C'è un bordo tra i nodi 0 e 4 e una connessione diretta tra 0 e 4. Ma a causa del grafico non diretto, c'è anche una connessione tra 4 e 0. Ecco perché se si esamina l'elenco di adiacenza precedente, il vertice 4 punta anche al vertice 0. Lo stesso vale anche nel caso del vertice 3. L'elenco di adiacenza del vertice 3 punta anche al vertice 0.
Elenco di adiacenza grafico diretto
L'immagine sopra è un grafico diretto e sul lato destro è il suo elenco di adiacenza. In questo elenco di adiacenza, possiamo vedere un bordo diretto dal nodo 1 al nodo 2 ma non dal nodo da 2 a 1. Quindi, possiamo muoverci solo in una direzione, cioè da 1 a 2. Lo stesso è anche nell'elenco di adiacenza. Non possiamo vedere nessun collegamento dal vertice 2 a 1 nell'elenco di adiacenza di 2.
Matrice di adiacenza
La matrice viene utilizzata in questo metodo per rappresentare i dettagli dei vertici del grafico. La dimensione della matrice dipende dal numero di vertici nel grafico. Ad esempio, se un grafico ha 5 vertici, la dimensione della matrice sarà 5 x 5. In questo, la riga e la colonna sono i vertici stessi. La rappresentazione della matrice dell'elenco di adiacenza utilizza 1 o 0 per riempire la matrice. Il valore di 1 rappresenta un percorso dal vertice di riga alla colonna vertice, ma il valore di 0 non rappresenta il percorso tra il vertice della riga e il vertice della colonna.
Elenco di adiacenza della matrice grafica non diretta
Nell'elenco di adiacenza della matrice sopra, possiamo vedere che da A a E è il valore 0 perché non c'è percorso tra di loro. Quindi, abbiamo riempito quel valore con 0. Ma c'è un percorso dal vertice b a a, e abbiamo riempito quel valore con 1.
Elenco di adiacenza della matrice grafica diretta
Nell'elenco di adiacenza della matrice sopra diretta, possiamo vedere che da A a D è il valore 0 perché non esiste un percorso da A a D, ma un percorso esiste da D a A, quindi abbiamo riempito quel valore con 1.
Matrix di incidenza
La matrice viene utilizzata in questo metodo per rappresentare i dettagli dei vertici del grafico. La dimensione della matrice dipende dal numero di vertici e bordi totali nel grafico. Ad esempio, se un grafico ha 5 vertici e 7 bordi, le dimensioni della matrice saranno 5 x 7. I bordi rappresenteranno le colonne e i vertici saranno sul lato della riga. La rappresentazione della matrice dell'elenco di adiacenza utilizza 0, 1 o -1 per riempire i valori della matrice.
Il valore di 1 rappresenta un percorso in uscita dal vertice di riga a vertice colonna, ma il valore di 0 non rappresenta il percorso tra vertice di riga e vertice della colonna. Il valore di -1 rappresenta un percorso in arrivo verso il bordo del vertice della colonna.
Grafico diretto
Elenco di adiacenza del grafico diretto
Codice C ++ per l'elenco di adiacenza del grafico diretto
#includere
Utilizzo dello spazio dei nomi std;
// Sintassi per creare il nodo
nodo struct
valore int;
Nodo* Next;
;
// Questo memorizzerà i dettagli del bordo grafico (origine e destinazione)
struct graphedge
fonte int, destinazione;
;
Classe GraphadJacencyList
// Crea un nuovo nodo per l'elenco di adiacenza
Nodo* getneighbourvertex (int destinazione, nodo* head_node)
Nodo* new_node = new node;
new_node-> value = destinazione;
new_node-> next = head_node;
restituire new_node;
// memorizzerà il numero totale di nodi in un grafico
int numero_of_nodes;
pubblico:
Nodo ** head_node;
GraphadJacencyList (GraphEdge Graphedges [], int num, int numero_of_nodes)
// Allocazione della memoria dinamica
head_node = new node*[numero_of_nodes] ();
this-> Number_of_nodes = numero_of_nodes;
// Inizializza il dono di head per ogni bordo del grafico
per (int k = 0; k < number_of_nodes; k++)
head_node [k] = nullptr;
per (int k = 0; k < num; k++)
int source = graphedges [k].fonte;
int destinazione = graphedges [k].destinazione;
Nodo* new_node = getneighbourvertex (destinazione, head_node [sorgente]);
head_node [sorgente] = new_node;
~ GraficadjacencyList ()
per (int k = 0; k < number_of_nodes; k++)
delete [] head_node [k];
delete [] head_node;
;
void display (nodo* displayptr)
while (DisplayPtr != nullptr)
cout << " adjacency list -> " << displayptr->valore;
DisplayPtr = DisplayPtr-> Next;
cout << endl;
int main ()
GraphEdge Graphedges [] =
// questi sono valori xey che rappresentano un bordo da x a y
0, 1, 1, 2, 2, 0, 2, 1, 3, 2, 4, 1, 3, 4
;
// Numero totale di nodi da 0 a 5, quindi i nodi totali sono 6
int numero_of_nodes = 6;
// Questo metodo calcolerà il numero di bordi nel grafico
int num_edges = sizeof (graphedges)/sizeof (graphedges [0]);
// Crea il grafico
Grafico graphadjacencylist (graphedges, num_edges, numero_of_nodes);
// Visualizza l'elenco di adiacenza del grafico
per (int k = 0; k < number_of_nodes; k++)
cout << k;
Display (grafico.head_node [k]);
restituzione 0;
Produzione:
0 Elenco di adiacenza -> 1
1 elenco di adiacenza -> 2
2 Elenco di adiacenza -> 1 elenco di adiacenza -> 0
3 Elenco di adiacenza -> 4 Elenco di adiacenza -> 2
4 Elenco di adiacenza -> 1
5
Grafico diretto con bordi pesi
Elenco di adiacenza del grafico diretto
Codice C ++ per l'elenco di adiacenza del grafico diretto con peso
#includere
Utilizzo dello spazio dei nomi std;
// Sintassi per creare il nodo
nodo struct
valore int, costo;
Nodo* Next;
;
// Questo memorizzerà i dettagli del bordo grafico (origine e destinazione)
struct graphedge
Source, destinazione, bordo;
;
Classe GraphadJacencyList
// Crea un nuovo nodo per l'elenco di adiacenza
Node* GetNeighbourvertex (Int Destination, Int Edgeweight,
Nodo* head_node)
Nodo* new_node = new node;
new_node-> value = destinazione;
new_node-> cost = bordo;
new_node-> next = head_node;
restituire new_node;
// memorizzerà il numero totale di nodi in un grafico
int numero_of_nodes;
pubblico:
Nodo ** head_node;
GraphadJacencyList (GraphEdge Graphedges [], int num, int numero_of_nodes)
// Allocazione della memoria dinamica
head_node = new node*[numero_of_nodes] ();
this-> Number_of_nodes = numero_of_nodes;
// Inizializza il dono di head per ogni bordo del grafico
per (int k = 0; k < number_of_nodes; k++)
head_node [k] = nullptr;
per (int k = 0; k < num; k++)
int source = graphedges [k].fonte;
int destinazione = graphedges [k].destinazione;
int edgeweight = graphedges [k].bordo;
Nodo* new_node = getneighbourvertex (destinazione, bordo,
head_node [sorgente]);
head_node [sorgente] = new_node;
GraphadJacencyList ()
per (int k = 0; k < number_of_nodes; k++)
delete [] head_node [k];
delete [] head_node;
;
void display (nodo* displayptr, int k)
while (DisplayPtr != nullptr)
cout << "(" << k << ", " <<
DisplayPtr-> Valore << ", " << displayptr->costo << ") ";
DisplayPtr = DisplayPtr-> Next;
cout << endl;
int main ()
GraphEdge Graphedges [] =
// (x, y, z) => Questi sono valori xey che rappresentano un bordo
// da x a y con peso w
0, 1, 4, 1, 2, 6, 2, 0, 3, 2, 1, 5, 3, 4, 8,
4, 1, 1, 3, 2, 7
;
// Numero totale di nodi da 0 a 5, quindi i nodi totali sono 6
int numero_of_nodes = 6;
// Questo metodo calcolerà il numero di bordi nel grafico
int num_edges = sizeof (graphedges)/sizeof (graphedges [0]);
// Crea il grafico
Grafico graphadjacencylist (graphedges, num_edges, numero_of_nodes);
// Visualizza l'elenco di adiacenza del grafico
per (int k = 0; k < number_of_nodes; k++)
cout << k;
Display (grafico.head_node [k], k);
restituzione 0;
Produzione:
0 (0, 1, 4)
1 (1, 2, 6)
2 (2, 1, 5) (2, 0, 3)
3 (3, 2, 7) (3, 4, 8)
4 (4, 1, 1)
5
Conclusione
In questo articolo, abbiamo visto metodi diversi per rappresentare il grafico. Abbiamo anche visto la matrice di incidenza, che è anche un metodo per rappresentare la matrice del grafico. Successivamente, abbiamo discusso di altri metodi di programmazione C ++ per rappresentare l'elenco di adiacenza (grafici diretti diretti e ponderati). Abbiamo anche studiato grafici diretti e indiretti. Abbiamo anche saputo che un grafico non orientato è facile da gestire rispetto a un grafico diretto perché un grafico non diretto è un grafico bidirezionale. Dopotutto, non dipende dalla direzione del bordo come il grafico diretto.