Wat is grafiekgegevensstructuur?

A Grafiek is een niet-lineaire datastructuur bestaande uit hoekpunten en randen. De hoekpunten worden soms ook knooppunten genoemd en de randen zijn lijnen of bogen die twee willekeurige knooppunten in de grafiek met elkaar verbinden. Meer formeel bestaat een grafiek uit een reeks hoekpunten ( IN ) en een reeks randen( EN ). De grafiek wordt aangegeven met G(V, E) .

Representaties van grafiek

Dit zijn de twee meest gebruikelijke manieren om een ​​grafiek weer te geven:

1. Nabijheidsmatrix
2. Nabijheidslijst

Nabijheidsmatrix

Een aangrenzende matrix is ​​een manier om een ​​grafiek weer te geven als een matrix van Booleaanse waarden (0-en en 1-en).

Laten we aannemen dat die er zijn N hoekpunten in de grafiek Maak dus een 2D-matrix bijvoeglijk naamwoordMat[n][n] met afmeting n x n.

• Als er een rand is vanaf het hoekpunt i naar J , markering bijvoeglijk naamwoordMat[i][j] als 1 .
• Als er geen rand is vanaf het hoekpunt i naar J , markering bijvoeglijk naamwoordMat[i][j] als 0 .

Weergave van ongerichte grafiek naar aangrenzende matrix:

De onderstaande afbeelding toont een ongerichte grafiek. In eerste instantie wordt de gehele Matrix geïnitialiseerd 0 . Als er een rand is van bron naar bestemming, voegen we deze in 1 voor beide gevallen ( bijvoeglijk naamwoord[bestemming] En bijvoeglijk naamwoord [ bestemming]) omdat we beide kanten op kunnen gaan.

Ongerichte grafiek naar aangrenzende matrix

string.format java

Weergave van gerichte grafiek naar aangrenzende matrix:

De onderstaande afbeelding toont een gerichte grafiek. In eerste instantie wordt de gehele Matrix geïnitialiseerd 0 . Als er een rand is van bron naar bestemming, voegen we deze in 1 voor dat specifieke bijvoeglijk naamwoord[bestemming] .

Gerichte grafiek naar aangrenzende matrix

Nabijheidslijst

Een array van lijsten wordt gebruikt om randen tussen twee hoekpunten op te slaan. De grootte van de array is gelijk aan het aantal hoekpunten (dwz n) . Elke index in deze array vertegenwoordigt een specifiek hoekpunt in de grafiek. De vermelding bij de index i van de array bevat een gekoppelde lijst met de hoekpunten die grenzen aan het hoekpunt i .

Laten we aannemen dat die er zijn N hoekpunten in de grafiek Maak dus een reeks van lijst van grootte N als adjLijst[n].

• adjList[0] zal alle knooppunten bevatten die verbonden zijn (buur) met het hoekpunt 0 .
• adjList[1] zal alle knooppunten bevatten die verbonden zijn (buur) met het hoekpunt 1 enzovoort.

Weergave van ongerichte grafiek naar aangrenzende lijst:

De onderstaande ongerichte grafiek heeft 3 hoekpunten. Er wordt dus een reeks lijsten gemaakt van grootte 3, waarbij elke indices de hoekpunten vertegenwoordigen. Nu heeft hoekpunt 0 twee buren (d.w.z. 1 en 2). Voeg dus hoekpunt 1 en 2 in op indices 0 van de array. Op dezelfde manier heeft het voor hoekpunt 1 twee buren (dat wil zeggen 2 en 0). Voeg dus hoekpunten 2 en 0 in op indices 1 van de array. Op dezelfde manier voegt u voor hoekpunt 2 de buren ervan in de array van de lijst in.

Ongerichte grafiek naar aangrenzende lijst

Weergave van gerichte grafiek naar aangrenzende lijst:

De onderstaande gerichte grafiek heeft 3 hoekpunten. Er wordt dus een reeks lijsten gemaakt van grootte 3, waarbij elke indices de hoekpunten vertegenwoordigen. Nu heeft hoekpunt 0 geen buren. Voor hoekpunt 1 heeft het twee buren (dat wil zeggen 0 en 2). Voeg dus hoekpunten 0 en 2 in op indices 1 van de array. Op dezelfde manier voegt u voor hoekpunt 2 de buren ervan in de array van de lijst in.

Grafiek naar aangrenzende lijst gestuurd