Een aangrenzende lijst is een gegevensstructuur die wordt gebruikt om een grafiek weer te geven, waarbij elk knooppunt in de grafiek een lijst met aangrenzende hoekpunten opslaat.
Grafiekweergave van gerichte grafiek naar aangrenzende lijst
Kenmerken van de aangrenzende lijst:
- De grootte van de matrix wordt bepaald door het aantal knooppunten in het netwerk.
- Het aantal grafiekranden kan eenvoudig worden berekend.
- De aangrenzende lijst is a grillige reeks .
Hoe maak je een nabijheidslijst?
Het is heel gemakkelijk en eenvoudig om een lijst met aangrenzende gebieden voor een grafiek samen te stellen. Hieronder staan bepaalde stappen die u moet volgen:
- Maak een array van gekoppelde lijsten van grootte N , waarbij N het aantal hoekpunten in de grafiek is.
- Maak een gekoppelde lijst met aangrenzende hoekpunten voor elk hoekpunt in de grafiek.
- Voor elke rand (u, v) in de grafiek, voeg toe in naar de gekoppelde lijst van in , en voeg toe in naar de gekoppelde lijst van in als de grafiek niet gericht is, voeg anders toe in naar de lijst van in als het wordt aangestuurd in naar in . (Bij gewogen grafieken het gewicht samen met de verbindingen opslaan).
Toepassingen van de aangrenzende lijst:
- Het algoritme van Dijkstra , Breedte eerste zoekopdracht , En Diepte eerste zoekopdracht gebruik aangrenzende lijsten om grafieken weer te geven.
- Afbeelding verwerken : Aangrenzende lijsten kunnen worden gebruikt om de aangrenzende relaties tussen pixels in een afbeelding weer te geven.
- Spelontwikkeling : deze lijsten kunnen worden gebruikt om informatie op te slaan over de verbindingen tussen verschillende gebieden of niveaus. De game-ontwikkelaars gebruiken grafieken om gamekaarten of niveaus weer te geven.
Voordelen van het gebruik van een aangrenzende lijst:
- Een aangrenzende lijst is eenvoudig en gemakkelijk te begrijpen.
- Randen aan een grafiek toevoegen of verwijderen is snel en eenvoudig.
Nadelen van het gebruik van een nabijheidslijst:
- In aangrenzende lijsten kan toegang tot de randen langer duren dan bij de aangrenzende matrix.
- Het vereist meer geheugen dan de aangrenzende matrix voor compacte grafieken.
Wat kun je nog meer lezen?
- Betekenis en definitie van de aangrenzende matrix in DSA
- Rand toevoegen en verwijderen in de weergave van een aangrenzende grafiek van een grafiek
- Converteer de aangrenzende matrix naar de aangrenzende lijstweergave van de grafiek
- Converteer de aangrenzende lijst naar de aangrenzende matrixweergave van een grafiek
- Vergelijking tussen aangrenzende lijst en aangrenzende matrixweergave van grafiek