Seznam sousedství

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 26. listopadu 2020; kontroly vyžadují 2 úpravy .

Seznam sousedství je jedním ze způsobů, jak reprezentovat graf jako kolekci seznamů vrcholů. Každý vrchol grafu odpovídá seznamu sestávajícím ze „sousedů“ tohoto vrcholu.

Funkce implementace

Graf na obrázku výše má následující seznam sousedství:
A	přilehlý k	před naším letopočtem
b	přilehlý k	a, c
C	přilehlý k	a, b

Existuje několik variant zobrazení seznamu sousedství grafu, které se liší vlastnostmi asociace vrcholů a kolekcí sousedů, implementací kolekcí, zda jsou hrany a vrcholy zahrnuty v kolekcích sousedů nebo pouze vrcholy, způsoby reprezentace hran a vrcholů.

Implementace navržená Guido van Rossumem používá hashovací tabulku k přiřazení každého vrcholu k seznamu sousedních vrcholů. V této struktuře není žádná explicitní reprezentace hran [1] [2] .
Kormen a další navrhli implementaci, ve které jsou vrcholy reprezentovány číselným indexem v poli, ve kterém každá buňka v poli odkazuje na jednosměrně propojený seznam sousedních vrcholů. [3]
Objektově orientovaný seznam sousedství navržený Goodrichema Tamassie, obsahuje speciální vrcholové a okrajové třídy. Každý vrcholový objekt obsahuje odkaz na kolekci hran. Každý okrajový objekt obsahuje odkazy na odchozí a příchozí vrcholy. [čtyři]

Porovnání s maticí sousednosti

Srovnání s maticí sousedství
Úkon	seznam sousedství	Matice sousedství
Kontrola hrany (x,y)	$O(\|V\|)$	$O(1)$
Určení stupně vrcholu	$O(1)$	$O(\|V\|)$
Využití paměti pro řídké grafy	$O(\|V\|+\|E\|)$	$O(\|V\|^{2})$
Vložit/smazat obličej	$O(1)$	$O(d)$
Procházení grafu	$O(\|V\|+\|E\|)$	$O(\|V\|^{2})$

Odkazy

↑ Guido van Rossum . Python Patterns - Implementing Graphs (1998). Získáno 4. července 2016. Archivováno z originálu dne 25. června 2016. (neurčitý)
↑ Multimapa u guavy . Získáno 4. července 2016. Archivováno z originálu 1. února 2019. (neurčitý)
↑ Thomas H. Cormen ; Charles E. Leiserson ; Ronald L. Rivest ; Clifford Stein . Úvod do algoritmů , druhé vydání . - MIT Press a McGraw-Hill, 2001. - S. 527-529 sekce 22.1: Zobrazení grafů. — ISBN 0-262-03293-7 .
↑ Michael T. Goodrich a Roberto Tamassia. Návrh algoritmu : základy, analýza a příklady internetu . - John Wiley & Sons , 2002. - ISBN 0-471-38365-1 .
↑ Steven SkienaThe Algorithm Design Manual (2nd ed.) (neurčité) . - 2010. - S. 152 oddílu 5.2: Datové struktury pro grafy. — ISBN 0-387-00163-8 .