An seznam sosedov je podatkovna struktura, ki se uporablja za predstavitev grafa, kjer vsako vozlišče v grafu shrani seznam svojih sosednjih vozlišč.
Grafska predstavitev usmerjenega grafa na seznam sosednosti
Značilnosti seznama sosednosti:
- Velikost matrike je določena s številom vozlišč v omrežju.
- Število robov grafa je enostavno izračunati.
- Seznam sosednosti je a nazobčan niz .
Kako sestaviti seznam sosednosti?
Zelo lahko in preprosto je sestaviti seznam sosednosti za graf, spodaj so navedeni določeni koraki, ki jih morate upoštevati:
- Ustvarite niz povezanih seznamov velikosti n , kjer je N število vozlišč v grafu.
- Ustvarite povezan seznam sosednjih vozlišč za vsako vozlišče v grafu.
- Za vsak rob (u, v) v grafu dodajte v na povezani seznam v , in dodajte v na povezani seznam v če je graf neusmerjen drugače dodajte v na seznam v če je usmerjen iz v do v . (V primeru uteženih grafov shranite težo skupaj s povezavami).
Uporaba seznama sosednosti:
- Dijkstrajev algoritem , Najprej iskanje v širino , in Najprej iskanje po globini uporabite sezname sosednosti za predstavitev grafov.
- Obdelava slik : Sezname sosednosti lahko uporabite za predstavitev razmerij sosednosti med slikovnimi pikami na sliki.
- Razvoj iger : Te sezname je mogoče uporabiti za shranjevanje informacij o povezavah med različnimi območji ali ravnmi, ki jih razvijalci iger uporabljajo z grafi za predstavitev zemljevidov ali ravni iger.
Prednosti uporabe seznama sosednosti:
- Seznam sosednosti je preprost in lahko razumljiv.
- Dodajanje ali odstranjevanje robov iz grafa je hitro in enostavno.
Slabosti uporabe seznama sosednosti:
- Na seznamih sosednosti lahko dostop do robov traja dlje kot dostop do matrike sosednosti.
- Zahteva več pomnilnika kot matrika sosednosti za goste grafe.
Kaj še lahko berete?
- Pomen in definicija matrike sosednosti v DSA
- Dodajte in odstranite rob v predstavitvi seznama sosednosti grafa
- Pretvori matriko sosednosti v predstavitev grafa s seznamom sosednosti
- Pretvori seznam sosednosti v predstavitev grafa v matriki sosednosti
- Primerjava med seznamom sosednosti in predstavitvijo grafa v matriki sosednosti