Aangrenzende lijst en matrixweergave van grafiek

Ook al zien ze er allemaal anders uit soorten grafieken kan op een vergelijkbare manier worden weergegeven. Er zijn over het algemeen twee soorten grafiekweergave:

1. Nabijheid Matrix
2. Nabijheidslijst

Nabijheidslijst

Aangrenzende lijst bestaat uit gekoppelde lijsten. Elk hoekpunt wordt beschouwd als een array-index en elk element vertegenwoordigt een gekoppelde lijst. Deze gekoppelde lijsten bevatten de hoekpunten die randen hebben met het indexhoekpunt.

Hier is een voorbeeld van een lijst met aangrenzende gebieden:

Laten we zeggen dat een grafiek een V-aantal hoekpunten en een E-aantal randen bevat.

Over het algemeen zal de ruimtelijke complexiteit zijn: O(V + E).

De ergste ruimtelijke complexiteit zal zijn: O(V2) als de gegeven grafiek de volledige grafiek is

Nabijheid Matrix

Aangrenzende matrix bestaat uit een 2D-array. Grafiek met een V-aantal hoekpunten, de grootte van de matrix zal zijn VxV.

Zeggen, matrix[i][j] = 5. Het betekent dat er een rand is tussen knooppunt i en j, met een gewicht van 5.

Laten we eens kijken naar de volgende grafiek en de bijbehorende adjacentiematrix:

We hebben de 2D-reeks met behulp van deze stappen:

Stap 1) Hoekpunt A heeft een directe rand met B en het gewicht is 5. De cel in rij A en kolom B worden dus gevuld met 5. De rest van de cellen in rij A worden gevuld met nul.

Stap 2) Hoekpunten B hebben een directe rand met C en het gewicht is 4. De cel in rij B en kolom C worden dus gevuld met 4. De overige cellen in rij B worden gevuld met nul omdat B geen uitgaande rand heeft naar welke hoek dan ook. andere knooppunten.

Stap 3) Hoekpunten C hebben geen directe randen met andere hoekpunten. Rij C wordt dus gevuld met nullen.

Stap 4) Hoekpunt D heeft een gerichte rand met A en C.

• Hier heeft de cel in rij D en kolom A de waarde 7. De cellen in rij D en kolom C hebben de waarde 2.
• De rest van de cellen in rij D worden gevuld met nullen.

Stap 5) Hoekpunten E hebben een gerichte rand met B en D. De cel in rij E en kolom B heeft een waarde van 6. Cellen in rij E en kolom D hebben een waarde van 3. De rest van de cellen in rij D zijn gevuld met nullen.

Hier zijn enkele aandachtspunten:

• De grafiek heeft geen zelflussen als de primaire diagonaal van de aangrenzende matrix 0 is.
• De grafiek is een gerichte grafiek als de indexen (a,b) en (b,a) niet dezelfde waarde hebben. Anders is de grafiek een gerichte grafiek.
• De grafiek is een gewogen grafiek als de waarde van de cellen groter is dan 1.

Er is een probleem met de aangrenzende matrix, omdat deze vierkante spaties vereist. Hier slaan we de randen op die niet met elkaar verbonden zijn. Deze randen wijzen ruimte in het geheugen toe.

Als we bijvoorbeeld een grafiek met 100 knooppunten hebben, zijn er 10 cellen nodig om deze in de grafiek op te slaan. RAM. Met minder randen in de grafiek kan het toewijzen van zo'n groot geheugen een verspilling zijn. Dus de ruimtecomplexiteit met behulp van de Adjacency-matrix zal O(N2), waarbij N het aantal knooppunten in de grafiek betekent.