Seznam sousedů

V algoritmizace , An seznam sousedů je datová struktura používá k reprezentaci grafu .

Tato reprezentace je zvláště vhodná pro řídké grafy (to znamená ne příliš husté ), na rozdíl od matice sousedství přizpůsobené hustým grafům.

Definice a vlastnosti

Seznam sousedství neorientovaného grafu je seznam sousedů každého vrcholu. Orientovaný graf je obvykle pro každý vrchol seznam uzlů v čele každého okraje, který má vrchol jako jeho ocas.

Jedná se o relativně kompaktní zobrazení, když existuje několik hran (dutý graf), protože globální seznam obsahuje 2 m prvků, kde m je počet hran.

Implementace

Reprezentace grafu podle seznamu sousedů sdružuje s každým vrcholem grafu kolekci jeho sousedů jako vrcholy nebo hrany. Existuje mnoho variací tohoto základního principu, které se liší v detailech v implementaci asociace mezi vrcholy a těmito kolekcemi a v implementaci těchto kolekcí samotných, v závislosti na tom, zda obsahují jako základní prvek dva vrcholy hrany nebo hrany jako objekt, nebo pouze sousední vrcholy, nebo při výběru typů objektů použitých k reprezentaci vrcholů a seznamu hran.

Reprezentace grafů podle seznamu sousedství upřednostňují přístup více zaměřený na vrcholy. Existuje mnoho možných implementací seznamů sousedství:

Implementace Pythonu doporučená Guidem van Rossumem používá hašovací tabulku, aby asociovala s každým vrcholem grafu tabulku sousedních vrcholů. V této reprezentaci může být vrchol reprezentován jakýmkoli objektem, který lze hašovat. Neexistuje žádná explicitní reprezentace hran jako objektů.
Kniha od Cormena a kol. poskytuje implementaci, ve které jsou vrcholy reprezentovány čísly indexů. Jejich reprezentace používá pole indexované podle čísel vrcholů, ve kterém buňka odpovídajícího pole ukazuje na propojený seznam vrcholů sousedících s tímto vrcholem. V této reprezentaci lze prvky propojeného seznamu interpretovat jako hrany; neukládají však úplné informace o každém okraji, ale pouze o druhý konec okraje, a v neorientovaných grafech budou pro každou hranu dvě různé propojené položky seznamu (jedna v seznamech pro každý ze dvou konců hřebene ).
V objektově orientovaném programování má struktura známá jako seznam dopadů, kterou ve své knize navrhli například Goodrich a Tamassia, třídy objektů pro vrcholy a hrany. Každý vrcholový objekt má proměnnou instance ukazující na kolekci, která obsahuje seznam objektů, které jsou hranami incidentů. Každá hrana zase ukazuje na dva vrcholové objekty, které jsou jejími konci. Tato verze seznamu sousedství používá více paměti než verze, ve které jsou přímo uvedeny sousední vrcholy, ale existence explicitních hranových objektů umožňuje větší flexibilitu, například pro ukládání dalších informací o hranách.

Operace

Hlavní operací prováděnou datovou strukturou seznamu sousedství je poskytnout seznam sousedů daného vrcholu. Pomocí jedné z výše popsaných implementací to lze provést v konstantním čase na souseda. Jinými slovy, celkový čas pro výčet všech sousedů vrcholu je úměrný stupni vrcholu.

Můžete také použít seznamy sousedství k otestování, zda hrana existuje mezi dvěma danými vrcholy, ale toto znázornění není efektivní. V seznamu přilehlosti ve kterém sousedi každého vrcholu se netřídí, test na existenci okraje může být provedeno v čase úměrnou stupni jedné ze dvou uvedených vrcholů, za použití sekvenční chodit sousedy tohoto summitu. Pokud jsou sousedé reprezentováni jako seřazené pole, lze místo nich použít dichotomické vyhledávání , v čase úměrném logaritmu stupně.

Kompromis ve vesmíru

Hlavní alternativa k seznamu přilehlosti je sousednosti matice , je matice , jejíž řádky a sloupce jsou indexovány vrcholy a jejichž buňky obsahují logická hodnota, která označuje, zda existuje hrana mezi vrcholy, které odpovídají řádku. A sloupec buňky. Pro řídký graf (graf, který má jen několik okrajů) je seznam sousedství mnohem efektivnější z hlediska prostoru než matice sousedství uložená v poli): prostor požadovaný seznamem sousedství je úměrný počtu hran a vrcholů v grafu, zatímco pro matici sousedství uloženou v poli je prostor úměrný druhé mocnině počtu vrcholů. Je však možné ukládat sousední matice efektivnějším způsobem prostorově, v blízkosti lineárního lineárního prostoru převzatého ze seznamu sousedství, pomocí hašovací tabulky indexované dvojicemi vrcholů spíše než maticí. Jelikož každá položka v matici sousedství vyžaduje pouze jeden bit, lze ji představit velmi kompaktně a zabírat v prostoru pouze sousedící bajty. Kromě zamezení plýtvání prostorem podporuje tato kompaktnost princip lokality . ${| V |} ^ {2} / 8$

U řídkého grafu však seznamy sousedství vyžadují méně úložného prostoru, protože nepředstavují chybějící hrany. Takže pomocí implementace naivního pole na 32bitovém počítači vyžaduje seznam sousedů pro neorientovaný graf přibližně bajty. Jednoduchý graf může mít nejvíce hran, pokud povolíme smyčky. Všimněte si hustoty grafu. Reprezentace seznamu sousedů zabírá více místa než if , tedy pokud je to maticová reprezentace . Graf tedy musí být skutečně prázdný, aby ospravedlnil reprezentaci seznamem sousedů. $8 | E |$ $| V | ^ {2}$ $d = | E | / | V | ^ {2}$ $8 | E |> | V | ^ {2} / 8$ $d> 1/64$

Kromě vesmírného kompromisu obě datové struktury také usnadňují různé operace. Nalezení všech vrcholů sousedících s daným vrcholem v seznamu sousedství je stejně snadné jako procházení seznamu. Spíše s maticí sousedství musí být skenován celý řádek, což trvá dlouho . Existenci hrany mezi dvěma danými vrcholy lze určit v konstantním čase v matici sousedství, přičemž je vyžadován čas úměrný minimálnímu stupni dvou vrcholů v seznamu sousedů. $O (| V |)$

Poznámky a odkazy

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest a Clifford Stein , Úvod do algoritmiky , Dunod ,2002[ detail vydání ]
Guido van Rossum , „ Pythonské vzory - implementace grafů “ ,1998
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest a Clifford Stein , Úvod do algoritmiky , Dunod ,2002[ detail vydání ], část 22.1: Reprezentace grafů.
Michael T. Goodrich a Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet examples , John Wiley & Sons ,2002, 708 s. ( ISBN 0-471-38365-1 ).

externí odkazy

David Eppstein , „ Poznámky k přednášce ICS 161: Algoritmy grafů “ ,1996
Softwarová knihovna Boost implementuje efektivní seznam sousedství .
Knihovna Otevřené datové struktury (v Javě) obsahuje strukturu seznamu sousedství: Otevřené datové struktury - Oddíl 12.2 - AdjacencyList: Graf jako sbírka seznamů .