Szomszédsági lista

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. november 26-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A szomszédsági lista az egyik módja annak, hogy a gráfot csúcslisták gyűjteményeként ábrázoljuk . A gráf minden csúcsa megfelel egy listának, amely a csúcs "szomszédjaiból" áll.

Megvalósítási jellemzők

A fenti képen látható grafikon a következő szomszédsági listát tartalmazza:
a	szomszédos	időszámításunk előtt
b	szomszédos	a, c
c	szomszédos	a, b

A gráf szomszédsági listás ábrázolásának számos változata létezik, amelyek különböznek a csúcsasszociáció és a szomszédok gyűjteményének jellemzőiben, a gyűjtemények megvalósításában, abban, hogy élek és csúcsok szerepelnek-e a szomszédos gyűjteményekben, vagy csak csúcsok, az élek és csúcsok ábrázolásának módja.

A Guido van Rossum által javasolt megvalósítás egy hash táblát használ, hogy minden csúcsot a szomszédos csúcsok listájához társítson. Ebben a struktúrában nincs kifejezett élek ábrázolása [1] [2] .
Kormen és mások olyan megvalósítást javasoltak, amelyben a csúcsokat egy numerikus index képviseli egy tömbben, amelyben a tömb minden egyes cellája a szomszédos csúcsok egyirányú összekapcsolt listájára hivatkozik. [3]
Goodrich által javasolt objektum-orientált szomszédsági listaés Tamassia, speciális csúcs- és élosztályokat tartalmaz. Minden csúcsobjektum tartalmaz egy hivatkozást élek gyűjteményére. Minden élobjektum hivatkozásokat tartalmaz a kimenő és bejövő csúcsokra. [négy]

Összehasonlítás a szomszédsági mátrixszal

Összehasonlítás az Adjacency Matrix-szal
Művelet	szomszédsági lista	Szomszédsági mátrix
Él keresése (x,y)	$O(\|V\|)$	$O(1)$
Csúcs fokának meghatározása	$O(1)$	$O(\|V\|)$
Memóriahasználat ritka grafikonokhoz	$O(\|V\|+\|E\|)$	$O(\|V\|^{2})$
Arc beszúrása/törlése	$O(1)$	$O(d)$
Grafikon bejárás	$O(\|V\|+\|E\|)$	$O(\|V\|^{2})$

Linkek

↑ Guido van Rossum . Python Patterns - Implementing Graphs (1998). Letöltve: 2016. július 4. Az eredetiből archiválva : 2016. június 25. (határozatlan)
↑ Multimap és guava . Letöltve: 2016. július 4. Az eredetiből archiválva : 2019. február 1.. (határozatlan)
↑ Thomas H. Cormen ; Charles E. Leiserson ; Ronald L. Rivest ; Clifford Stein . Bevezetés az algoritmusokba , második kiadás . - MIT Press és McGraw-Hill, 2001. - 527-529. o., 22.1. szakasz: Grafikonok ábrázolása. — ISBN 0-262-03293-7 .
↑ Michael T. Goodrich és Roberto Tamassia. Algoritmustervezés : alapok, elemzés és internetes példák . - John Wiley & Sons , 2002. - ISBN 0-471-38365-1 .
↑ Steven SkienaThe Algorithm Design Manual (2. kiadás) (határozatlan idejű) . - 2010. - 152. o.: 5.2. szakasz: Grafikonok adatstruktúrái. — ISBN 0-387-00163-8 .