An zoznam susedstva je dátová štruktúra používaná na reprezentáciu grafu, kde každý uzol v grafe ukladá zoznam svojich susedných vrcholov.
Grafová reprezentácia riadeného grafu so zoznamom susedstva
Charakteristiky zoznamu susedstva:
- Veľkosť matice je určená počtom uzlov v sieti.
- Počet hrán grafu sa dá ľahko vypočítať.
- Zoznam susedstva je a zubaté pole .
Ako vytvoriť zoznam susedstva?
Je veľmi ľahké a jednoduché zostaviť zoznam susediacich grafov, existujú určité kroky uvedené nižšie, ktoré musíte dodržať:
- Vytvorte pole prepojených zoznamov veľkostí N , kde N je počet vrcholov v grafe.
- Vytvorte prepojený zoznam susedných vrcholov pre každý vrchol v grafe.
- Pre každú hranu (u, v) v grafe pridajte v do prepojeného zoznamu v a pridajte v do prepojeného zoznamu v ak je graf neorientovaný inak pridajte v do zoznamu v ak smeruje z v do v . (V prípade vážených grafov uložte hmotnosť spolu s pripojeniami).
Aplikácie zoznamu susedstva:
- Dijkstrov algoritmus , Prvé vyhľadávanie podľa šírky , a Hĺbkové prvé vyhľadávanie použite priľahlé zoznamy na znázornenie grafov.
- Spracovanie obrazu : Zoznamy susedstva možno použiť na znázornenie vzťahov susedstva medzi pixelmi v obrázku.
- Vývoj hier : Tieto zoznamy možno použiť na ukladanie informácií o prepojeniach medzi rôznymi oblasťami alebo úrovňami, ktoré vývojári hier používajú na znázornenie herných máp alebo úrovní pomocou grafov.
Výhody použitia zoznamu susedstva:
- Zoznam susedstva je jednoduchý a ľahko pochopiteľný.
- Pridávanie alebo odstraňovanie hrán z grafu je rýchle a jednoduché.
Nevýhody používania zoznamu susedstva:
- V susedných zoznamoch môže prístup k okrajom trvať dlhšie ako matica susedstva.
- Vyžaduje viac pamäte ako matica susednosti pre husté grafy.
Čo ešte môžeš čítať?
- Význam a definícia matice susednosti v DSA
- Pridať a odstrániť okraj v zobrazení zoznamu susediacich grafov
- Previesť maticu susednosti na zobrazenie zoznamu priľahlosti grafu
- Previesť zoznam susedstva na reprezentáciu grafu maticou susedstva
- Porovnanie medzi Adjacency List a Adjacency Matrix reprezentáciou grafu