Aangrenzende lijst en matrixweergave van grafiek
Sara Chen
⚡ Slimme samenvatting
Een aangrenzingslijst en een aangrenzingsmatrix representeren een graaf door knooppunten en verbindingen in het geheugen op te slaan, waardoor algoritmen netwerken kunnen doorlopen. Een aangrenzingslijst gebruikt gekoppelde lijsten per knooppunt, terwijl een aangrenzingsmatrix een vierkant tweedimensionaal raster gebruikt.
Ook al zien ze er allemaal anders uit soorten grafieken kan op een vergelijkbare manier worden weergegeven. Er zijn over het algemeen twee soorten grafische weergaven:
- Nabijheid Matrix
- Nabijheidslijst
Nabijheidslijst
Een aangrenzingslijst bestaat uit gekoppelde lijsten. Elk knooppunt wordt beschouwd als een array-index en elk element vertegenwoordigt een gekoppelde lijst. Deze gekoppelde lijsten bevatten de knooppunten die een gemeenschappelijke rand delen met het indexknooppunt.
Hier volgt een voorbeeld van een aangrenzingslijst:
Stel dat een graaf V knooppunten en E randen bevat. De ruimtecomplexiteit van de aangrenzingslijst is O(V + E), wat schaalt met het aantal werkelijke randen in plaats van elk mogelijk paar hoekpunten.
De ruimtecomplexiteit in het slechtste geval wordt O(V²) Als de gegeven graaf een complete graaf is, omdat elk knooppunt dan met elk ander knooppunt verbonden is.
Nabijheid Matrix
Een adjacentiematrix bestaat uit een tweedimensionale array. Voor een graaf met V knooppunten zal de grootte van de matrix zijn: V × V.
Zeg matrix[i][j] = 5Dit betekent dat er een verbinding is tussen knooppunt i en knooppunt j met een gewicht van 5.
Laten we de volgende graaf en de bijbehorende adjacentiematrix eens bekijken:
We hebben de 2D-reeks met behulp van deze stappen:
Stap 1) Knooppunt A heeft een directe verbinding met B, en het gewicht is 5. Dus de cel in rij A en kolom B wordt gevuld met 5. De overige cellen in rij A worden gevuld met nullen.
Stap 2) Knooppunt B heeft een directe verbinding met C, en het gewicht is 4. De cel in rij B en kolom C wordt dus gevuld met 4. De overige cellen in rij B worden gevuld met nullen, omdat B geen uitgaande verbinding heeft met een ander knooppunt.
Stap 3) Hoekpunt C heeft geen directe verbindingen met andere hoekpunten. Rij C zal dus gevuld worden met nullen.
Stap 4) Hoekpunt D heeft een gerichte verbinding met A en C.
- De cel in rij D en kolom A zal de waarde 7 hebben. De cel in rij D en kolom C zal de waarde 2 hebben.
- De rest van de cellen in rij D worden gevuld met nullen.
Stap 5) Hoekpunt E heeft een gerichte verbinding met B en D. De cel in rij E en kolom B krijgt de waarde 6. De cel in rij E en kolom D krijgt de waarde 3. De overige cellen in rij E worden gevuld met nullen.
Hier zijn enkele aandachtspunten:
- De graaf bevat geen zelflussen wanneer de primaire diagonaal van de adjacentiematrix 0 is.
- Een graaf is een gerichte graaf als de cellen op de posities (a, b) en (b, a) niet dezelfde waarde hebben. Anders is de graaf ongericht.
- Een grafiek is een gewogen grafiek als de waarde in een willekeurige cel groter is dan 1.
Het grootste probleem met de adjacentiematrix is dat deze vierkante geheugenruimte vereist. Zelfs randen die niet bestaan, nemen geheugencellen in beslag.
Als we bijvoorbeeld een grafiek hebben met 100 knooppunten, dan zijn er 10,000 cellen nodig om deze op te slaan. RAMMet minder randen in de graaf kan het toewijzen van zo'n groot geheugen verspilling zijn. De ruimtecomplexiteit bij gebruik van de adjacentiematrix is daarom... O(N²), waarbij N het aantal knooppunten in de graaf is.
Aangrenzingslijst versus aangrenzingsmatrix
Voordat je een representatie kiest, is het nuttig om beide modellen naast elkaar te vergelijken aan de hand van de bewerkingen die in de praktijk vaak voorkomen bij grafiekworkloads:
| Werking | Nabijheid Matrix | Nabijheidslijst |
|---|---|---|
| Ruimtecomplexiteit | O(V²) | O(V + E) |
| Voeg een hoekpunt toe | O(V²) | O (1) |
| Voeg een rand toe | O (1) | O (1) |
| Verwijder een rand | O (1) | O(E) |
| Controleer of de verbinding (i, j) bestaat. | O (1) | O(graad van i) |
| Doorloop de buren van i. | O (V) | O(graad van i) |
| Best voor | Dichte grafieken, frequente randquery's | Dunne grafieken, taken die veel doorloop vereisen |
Kortom, een adjacentiematrix is beter in het vinden van randen in constante tijd, terwijl een adjacentielijst beter presteert op het gebied van geheugen en het aantal iteraties naar buren. Daarom worden algoritmen zoals BFS, DFS en Dijkstra meestal gecombineerd met adjacentielijsten.
Voordelen en nadelen van grafische weergave
Elke weergave kent zijn eigen voor- en nadelen. Door de sterke en zwakke punten van beide modellen te kennen, kun je het juiste model kiezen voor het probleem dat je probeert op te lossen.
Voordelen van de aangrenzingsmatrix:
- Constante-tijd O(1) zoekopdrachten naar het bestaan van randen tussen elk willekeurig paar knooppunten.
- Vaste indexering maakt matrixgebaseerde algoritmen zoals Floyd-Warshall en transitieve sluiting eenvoudig te implementeren.
- Gewogen randen passen van nature in één matrixcel.
Nadelen van de aangrenzingsmatrix:
- Verspilt O(V²) geheugen wanneer de grafiek dunbevolkt is.
- Het toevoegen van een nieuw hoekpunt vereist dat de gehele matrix wordt aangepast.
- Het doorlopen van de buren van een enkel knooppunt kost O(V), zelfs als het knooppunt maar een paar randen heeft.
Voordelen van een aangrenzingslijst:
- Gebruikt slechts O(V + E) geheugen, wat dicht in de buurt komt van het werkelijke aantal randen in dunne grafieken.
- Het toevoegen van een nieuw knooppunt of een nieuwe rand is O(1).
- Doorloopalgoritmen zoals BFS en DFS doorlopen buren in O(graad), wat resulteert in een totale looptijd van O(V + E).
Nadelen van een aangrenzingslijst:
- Controleren of een specifieke rand bestaat, kost O(graad) tijd in plaats van O(1).
- De cachelocaliteit is zwakker omdat gekoppelde lijsten verspreid over het geheugen staan.
- Gewogen randen vereisen een begeleidend veld of een lijst met paren, wat de datastructuur enigszins compliceert.
Wanneer gebruik je een aangrenzingslijst versus een aangrenzingsmatrix?
De keuze van de representatie hangt af van de dichtheid van de grafiek en de bewerkingen die u het vaakst uitvoert. Gebruik deze korte handleiding om de juiste structuur te kiezen:
- Geef de voorkeur aan de aangrenzingsmatrix. wanneer de graaf dicht is (E ligt dicht bij V²), wanneer randen zelden veranderen en wanneer je algoritme vaak de vraag stelt: "Is er een rand tussen i en j?".
- Geef de voorkeur aan de aangrenzingslijst. wanneer de graaf dunbevolkt is (E is veel kleiner dan V²), wanneer de verzameling knooppunten of randen groeit tijdens de uitvoering, en wanneer je de graaf doorloopt met BFS, DFS of Dijkstra's kortste-pad-algoritme.
- Geef de voorkeur aan een gemengd model. (aangrenzingslijst plus een hashset van randen) wanneer je zowel snelle buuriteratie als O(1) randquery's nodig hebt, ten koste van extra geheugen.
Moderne grafiekbibliotheken zoals NetworkX en igraph gebruiken standaard aangrenzingslijsten, omdat de meeste grafieken in de praktijk — sociale netwerken, wegenkaarten, webpagina's, pakketafhankelijkheden — dunbevolkt zijn en veel doorloopbewerkingen vereisen.
