Adjacency liste i C ++
- Adjacency liste
- Matrise av adjacency
- En forekomstmatrise
Denne artikkelens primære emne vil være adjacency -listen. La oss først prøve å forstå hva en graf virkelig er før vi kommer inn på den for å forstå denne ideen bedre.
Hva er en graf?
En graf har et fast antall noder eller hjørner. Og hver node er koblet sammen med en linje, som vi kaller en kant. Kanten er for kommunikasjon mellom to hjørner eller noder. I grafen ovenfor ser vi for eksempel seks hjørner eller noder (0, 1, 2, 3, 4 og 5). Fra toppunkt eller node 0 kan vi enkelt flytte til toppunkt 1 og 3 fordi det er en direkte forbindelse mellom dem. Men det er ingen direkte forbindelse mellom toppunkt eller node 0 og 4.
Grafer brukes i mange virkelige applikasjoner for å løse nettverksproblemer. For eksempel på Facebook er brukerens profil en node eller toppunkt, og brukerens venner på listen er ytterligere forskjellige noder eller toppunkter som har direkte tilkoblinger mellom dem.
Typer grafer
Det er først og fremst to typer grafer, ikke -rettede grafer og rettede grafer, begge er beskrevet i de neste seksjonene:
Ikke rettet graf
Den ikke-rettede grafen er veldig kjent fordi det er en toveis graf. Nedenfor er for eksempel et eksempel på en rettet graf:
Ikke rettet graf
I den rettede grafen kan vi flytte til ethvert toppunkt. For eksempel, hvis det er en forbindelse mellom noder A og B, kan vi også flytte fra B til A.
Regissert graf
I en rettet graf har kantene retningskanter. Så disse pilkantene vil fortelle oss hvordan vi kan bevege oss i grafen fra en toppunkt til et annet toppunkt, men bare under noen forhold. For eksempel, hvis det er en rettet kant mellom nodene A og B, kan vi raskt bevege oss fra toppunktet A til B, men ikke tilbake fra B til A hvis det ikke er noen rettet kant fra B til A.
Regissert graf
Adjacency liste
Adjacency -listen er en liste over matriser der størrelsen på matrisen er lik antall noder som er til stede i grafen. Og hver node har også en underarrang som representerer sin tilkobling til andre noder eller hjørner. Vi kommer til å diskutere adjacency -listene over begge typer grafer (ikke rettet og rettet).
Ikke rettet grafjacency liste
I ovennevnte graf kan vi se seks hjørner (0, 1, 2, 3, 4, 5). Så vi har en rekke seks hjørner. Og hver ytterligere individuell toppunkt har sin egen lenket liste eller adjacency -liste, som vist i forrige adjacency -liste. Vi kan se at Vertex 0 peker på Vertex 4 og Vertex 3.
Men som vi har forklart før, kan en rettet graf bevege seg i begge retninger. Det er en kant mellom noder 0 og 4 og en direkte forbindelse mellom 0 til 4. Men på grunn av den rettede grafen er det også en forbindelse mellom 4 til 0. Det er grunnen til at hvis du ser på den forrige adjacency -listen, peker Vertex 4 også på toppunktet 0. Det samme er også tilfelle i tilfelle av toppunkt 3. Adjacency -listen over toppunkt 3 peker også på toppunktet 0.
Regissert Graph Adjacency List
Bildet ovenfor er en rettet graf, og på høyre side er den adjacency -listen. I denne adjacency -listen kan vi se en direkte kant fra node 1 til node 2, men ikke fra node 2 til 1. Så vi kan bare bevege oss i en retning, det vil si fra 1 til 2. Det samme er også i adjacency -listen. Vi kan ikke se noen lenke fra Vertex 2 til 1 i adjacency -listen over 2.
Adjacency matrix
Matrisen brukes i denne metoden for å representere detaljene i grafhoderne. Størrelsen på matrisen avhenger av antall hjørner i grafen. For eksempel, hvis noen graf har 5 hjørner, vil størrelsen på matrisen være 5 x 5. I dette er raden og kolonnen toppunktene i seg selv. Matrixrepresentasjonen av adjacency -listen bruker enten 1 eller 0 for å fylle matrisen. Verdien på 1 representerer en bane fra Row Vertex til kolonneutvikling, men verdien av 0 representerer ingen bane mellom radhtex og kolonneutstyr.
Ikke rettet grafmatriseadjacency liste
I listen ovenfor Matrix Adjacency kan vi se at A til E er verdi 0 fordi det ikke er noen vei mellom dem. Så vi fylte den verdien med 0. Men det er en vei fra toppunkt B gjennom A, og vi fylte den verdien med 1.
Regissert graf Matrix Adjacency List
I den ovennevnte Matrix Adjacency-listen kan vi se at A til D er verdi 0 fordi det ikke er noen vei fra A til D, men en sti eksisterer fra D til A, så vi fylte den verdien med 1.
Forekomstmatrise
Matrisen brukes i denne metoden for å representere detaljene i grafhoderne. Størrelsen på matrisen avhenger av antall hjørner og totale kanter i grafen. For eksempel, hvis noen graf har 5 hjørner og 7 kanter, vil størrelsen på matrisen være 5 x 7. Kantene vil representere søylene, og toppunktene vil være på radsiden. Matriksrepresentasjonen av adjacency -listen bruker enten 0, 1 eller -1 for å fylle matriseverdiene.
Verdien på 1 representerer en utgående bane fra Row Vertex til kolonneutvikling, men verdien av 0 representerer ingen bane mellom radhtex og kolonneutstyr. Verdien på -1 representerer en innkommende bane til kanten av kolonnen Vertex.
Regissert graf
Adjacency List of Directed Graph
C ++ kode for listen
#inkludere
ved hjelp av navneområdet STD;
// Syntaks for å lage node
Struct Node
int verdi;
Node* Neste;
;
// dette vil lagre grafkantdetaljene (kilde og destinasjon)
struct graphEdge
int kilde, destinasjon;
;
klasse GraphadJacencyList
// Opprett en ny node for adjacency -listen
Node* getNeighbourVertex (int destinasjon, node* head_node)
Node* new_node = ny node;
new_node-> verdi = destinasjon;
new_node-> next = head_node;
return new_node;
// det vil lagre det totale antallet noder i en graf
int number_of_nodes;
offentlig:
Node ** head_node;
GraphadJacencyList (GraphEdge Graphedges [], int num, int number_of_nodes)
// Dynamisk minnetildeling
head_node = new node*[number_of_nodes] ();
dette-> number_of_nodes = number_of_nodes;
// Initialiser headnode for hver kant av grafen
for (int k = 0; k < number_of_nodes; k++)
head_node [k] = nullptr;
for (int k = 0; k < num; k++)
int source = graphedges [k].kilde;
int -destinasjon = grafer [k].mål;
Node* new_node = getNeighbourVertex (destinasjon, head_node [kilde]);
head_node [kilde] = new_node;
~ GraphadJacencyList ()
for (int k = 0; k < number_of_nodes; k++)
slett [] head_node [k];
slett [] head_node;
;
void display (node* displayPtr)
mens (DisplayPtr != nullptr)
cout << " adjacency list -> "" << displayptr->verdi;
DisplayPtr = DisplayPtr-> Neste;
cout << endl;
int main ()
GraphEdge Graphedges [] =
// dette er x- og y -verdier som representerer en kant fra x til y
0, 1, 1, 2, 2, 0, 2, 1, 3, 2, 4, 1, 3, 4
;
// Totalt antall noder fra 0 til 5, så totale noder er 6
int number_of_nodes = 6;
// Denne metoden beregner antall kanter i grafen
int num_edges = sizeOf (Graphedges)/sizeOf (Graphedges [0]);
// Lag grafen
GraphadJacencyList Graph (Graphedges, num_edges, number_of_nodes);
// Vis adjacency -listen over grafen
for (int k = 0; k < number_of_nodes; k++)
cout << k;
skjerm (graf.head_node [k]);
retur 0;
Produksjon:
0 adjacency liste -> 1
1 adjacency liste -> 2
2 Adjacency List -> 1 Adjacency List -> 0
3 Adjacency List -> 4 Adjacency List -> 2
4 Adjacency List -> 1
5
Regissert graf med vektkanter
Adjacency List of Directed Graph
C ++ -kode for den rettede grafadjacenslisten med vekt
#inkludere
ved hjelp av navneområdet STD;
// Syntaks for å lage node
struct node
int verdi, kostnad;
Node* Neste;
;
// dette vil lagre grafkantdetaljene (kilde og destinasjon)
struct graphEdge
int kilde, destinasjon, kantvekt;
;
klasse GraphadJacencyList
// Opprett en ny node for adjacency -listen
Node* getneighbourVertex (int -destinasjon, int kantvekt,
Node* head_node)
Node* new_node = ny node;
new_node-> verdi = destinasjon;
new_node-> cost = edgeweight;
new_node-> next = head_node;
return new_node;
// det vil lagre det totale antallet noder i en graf
int number_of_nodes;
offentlig:
Node ** head_node;
GraphadJacencyList (GraphEdge Graphedges [], int num, int number_of_nodes)
// Dynamisk minnetildeling
head_node = new node*[number_of_nodes] ();
dette-> number_of_nodes = number_of_nodes;
// Initialiser headnode for hver kant av grafen
for (int k = 0; k < number_of_nodes; k++)
head_node [k] = nullptr;
for (int k = 0; k < num; k++)
int source = graphedges [k].kilde;
int -destinasjon = grafer [k].mål;
int kantvekt = grafer [k].kantvekt;
Node* new_node = getNeighbourVertex (destinasjon, kantvekt,
head_node [kilde]);
head_node [kilde] = new_node;
GraphadJacencyList ()
for (int k = 0; k < number_of_nodes; k++)
slett [] head_node [k];
slett [] head_node;
;
void display (node* displayPtr, int k)
mens (DisplayPtr != nullptr)
cout << "(" << k << ", " <<
DisplayPtr-> Verdi << ", " << displayptr->koste << ") ";
DisplayPtr = DisplayPtr-> Neste;
cout << endl;
int main ()
GraphEdge Graphedges [] =
// (x, y, z) => disse er x og y verdier som representerer en kant
// fra x til y med vekt w
0, 1, 4, 1, 2, 6, 2, 0, 3, 2, 1, 5, 3, 4, 8,
4, 1, 1, 3, 2, 7
;
// Totalt antall noder fra 0 til 5, så totale noder er 6
int number_of_nodes = 6;
// Denne metoden beregner antall kanter i grafen
int num_edges = sizeOf (Graphedges)/sizeOf (Graphedges [0]);
// Lag grafen
GraphadJacencyList Graph (Graphedges, num_edges, number_of_nodes);
// Vis adjacency -listen over grafen
for (int k = 0; k < number_of_nodes; k++)
cout << k;
skjerm (graf.head_node [k], k);
retur 0;
Produksjon:
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
Konklusjon
I denne artikkelen har vi sett forskjellige metoder for å representere grafen. Vi har også sett forekomstmatrisen, som også er en metode for å representere grafmatrisen. Deretter diskuterte vi andre C ++ programmeringsmetoder for å representere adjacency -listen (rettet og vektede rettede grafer). Vi har også studert rettede og rettede grafer. Vi ble også kjent med at en rettet graf er enkel å håndtere sammenlignet med en rettet graf fordi en rettet graf er en toveis graf. Tross alt er det ikke kantretning avhengig som den rettede grafen.