Листа суседства

У теорији графова и компјутерским наукама , листа суседства представља граф као колекцију несортираних листи, једна за сваки чвор у графу. Свака листа описује скуп суседа свог темена.

Детаљи имплементације уреди

График на слици горе има представу листе суседства:
a	суседно са	b,c
b	суседно са	a,c
c	суседно са	a,b

Листа суседства презентује граф везама сваког чвора у графу са својим суседним теменима и ивицама. Постоје многе варијације са овом основном идејом. Разликују се у детаљима како се спроводи веза између групе чворова, у томе како они спроводе своје колекције, било да укључују и темена и ивице или темена само као прву класу објеката, у које врсте објеката се користе да би се представила темена и ивице.

Једна имплементација коју је предложио Гвидо ван Росум користи хеш табелу, удружити сваки чвор у графу са низом суседних темена. У овом представљању, чвор може бити представљен као било који хасхабле објекат. Не постоји експлицитна заступљеност ивица као објеката.^[1]
Cormen et al. предлазе имплементацију у којој су темена представљена индексом бројева.^[2] Њихово представљање користи низ индексиран од темена, број на којој низ ћелија за сваки чвор тачке једноструко повезане листе од суседних темена тог темена. У овом представљању, чворови на једноструко повезаној листи могу се тумачити као ивице објеката. Међутим, они не садрже потпуне информације о свакој ивици (они само складиште једну од две крајње тачке на ивици) и у неусмереним графовима ће бити повезане две различите повезане листе чворова за сваку ивицу (један у листама за сваки од две крајње тачке ивице ).
Објектно оријентисано инцидентна листа структура предложена од Goodrich-a и Tamassia имају посебне класе чворова објеката и објеката ивице. Сваки чвор објекат има променљиву која показује на колекцију објеката који су наведени у суседне ивице објекта. Заузврат, свака ивица објеката указује на два темена објекта на њеним крајњим тачкама.^[3] Ова верзија листе суседства користи више меморије од верзије у којој суседна темена су директно наведена, али постојање јасних ивица објеката омогућава додатну флексибилност у складиштење додатне информације о ивицама.

Операције уреди

Главни операција коју обавља структура података листе суседства је да пријави листу суседа датог темена. Користећи било коју од имплементација претходно описаних, ово се може извести у сталном време по суседима. Другим речима ,укупно време извештаваја за све суседе једног темена v је пропорционално степену v.

Такође је могћуе, али не тако ефикасно, да се користе листе суседства за тестирање да ли ивица постоји или не постоји између два наведена темена. У листи суседства у којој су несортирани суседи сваког чвора, тестирање за постојање ивице се може извршити за време пропорционално степену једног од два датих темена, помоћу секвенцијалне претраге кроз суседе овог чвора. Ако су комшије представљени као сортирани низ, бинарно претраживање може да се користи, узимање времена пропорционалног логаритму степена.

Алтернатива уреди

Главна алтернатива листи суседства је матрица суседства, матрица чији редови и колоне индексирају темена и чије ћелије садрже Боолеан вредност која означавају да ли је ивица присутна између темена који одговарају реду и колони ћелије. За оскудан графа (у којем већина парова темена нису повезани ивицама) листа суседства је знатно више просторно ефикаснија него матрице суседства (представљена као низ). Употреба простора за листу суседства је пропорционалан броју ивица и темена у графу, док за матрицу суседства складиштене на овај начин је пропорционално квадрату броја темена. Међутим, могуће је да се више простора - ефикасније складиштити матрица суседства тј. да одговара линеарном коришћењу простора једне листе суседства, коришћењем хеш табеле регистроване у паровима темена.

Други значајна разлика између листи суседства и матрица суседства је у ефикасности операција које обављају. У листи суседства, комшије сваког темена се могу ефикасно исписати, у времену пропорционалном степену темена. У матрици суседства, за ову операцију потребно време пропорционално је броју темена у графу, који може бити знатно већи од степена. С друге стране, матрица суседства дозвољава тестирање да ли два темена су један поред другог у сталном времену. Листа суседства је спорија код ове операције.

Структуре података уреди

За употребу као структуру података ,главна алтернатива матрице суседства је листа суседства. Јер сваки унос у матрици суседства захтева само један бит, може бити представљена у врло компактном облику , заузима само $|V|^{2}/8$ бајтова простора. Поред избегавања изгубљеног простора, ово компактност подстиче локалитет референце.

Међутим, за оскудан графа, листе суседства захтевају мање простора за складиштење , јер не губимо простор да представљамо ивице које нису присутне. Коришћење наивне имплементације низа на 32 - битном рачунару ,списак суседства на неусмереном графа захтева око $8|E|$ бајтова .

Констатујући да једноставни граф може имати највише $|V|^{2}$ ивице, омогућавајући петље, можемо рећи да $d=|E|/|V|^{2}$ означава густину графа. Затим , $8|E|>|V|^{2}/8$ , односно представљање листе суседства заузима више простора управо када $d>1/64$ . Тако да граф мора бити редак да би заиста оправдао коришчење листе суседства.

Поред простора компромису, различите структуре података и олакшати различите операције. Проналажење свих темена, суседна темена до датог у виду листи суседства је једноставно као читање листе. Са суседства матрице, цео ред мора уместо тога бити скениран, који траје $O(|V|)$ времена. Да ли постоји ивица између две датих темена могу да се одреде ођедном са матрицом суседства, а потребно време пропорционално минималном степену два темена са листом суседства.

Референце уреди

^ Guido van Rossum (1998). „Python Patterns — Implementing Graphs”.
^ Cormen, Thomas H.; Leiserson, Charles E.; Ronald L. Rivest; Stein, Clifford (2001). Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. стр. 527—529of section 22.1: Representations of graphs. ISBN 978-0-262-03293-3. Непознати параметар |auhtorlink= игнорисан (помоћ)
^ Goodrich, Michael T.; Roberto Tamassia (2002). Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. ISBN 978-0-471-38365-9.

Литература уреди

Goodrich, Michael T.; Roberto Tamassia (2002). Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. ISBN 978-0-471-38365-9.
Cormen, Thomas H.; Leiserson, Charles E.; Ronald L. Rivest; Stein, Clifford (2001). Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. стр. 527—529of section 22.1: Representations of graphs. ISBN 978-0-262-03293-3. Непознати параметар |auhtorlink= игнорисан (помоћ)

Додатно за читање уреди

Eppstein, David (1996). „ICS 161 Lecture Notes: Graph Algorithms”.

Спољашње везе уреди

The Boost Graph Library implements an efficient adjacency list
Open Data Structures - Section 12.2 - AdjacencyList: A Graph as a Collection of Lists

[1] Guido van Rossum (1998). „Python Patterns — Implementing Graphs”.

[2] Cormen, Thomas H.; Leiserson, Charles E.; Ronald L. Rivest; Stein, Clifford (2001). Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. стр. 527—529of section 22.1: Representations of graphs. ISBN 978-0-262-03293-3. Непознати параметар |auhtorlink= игнорисан (помоћ)

[A-3] Goodrich, Michael T.; Roberto Tamassia (2002). Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. ISBN 978-0-471-38365-9.

[1]

[2]

[3]