Lista susedstva

U teoriji grafova i kompjuterskim naukama , lista susedstva predstavlja graf kao kolekciju nesortiranih listi, jedna za svaki čvor u grafu. Svaka lista opisuje skup suseda svog temena.

Detalji implementacije uredi

Grafik na slici gore ima predstavu liste susedstva:
a	susedno sa	b,c
b	susedno sa	a,c
c	susedno sa	a,b

Lista susedstva prezentuje graf vezama svakog čvora u grafu sa svojim susednim temenima i ivicama. Postoje mnoge varijacije sa ovom osnovnom idejom. Razlikuju se u detaljima kako se sprovodi veza između grupe čvorova, u tome kako oni sprovode svoje kolekcije, bilo da uključuju i temena i ivice ili temena samo kao prvu klasu objekata, u koje vrste objekata se koriste da bi se predstavila temena i ivice.

Jedna implementacija koju je predložio Gvido van Rosum koristi heš tabelu, udružiti svaki čvor u grafu sa nizom susednih temena. U ovom predstavljanju, čvor može biti predstavljen kao bilo koji hashable objekat. Ne postoji eksplicitna zastupljenost ivica kao objekata.^[1]
Cormen et al. predlaze implementaciju u kojoj su temena predstavljena indeksom brojeva.^[2] Njihovo predstavljanje koristi niz indeksiran od temena, broj na kojoj niz ćelija za svaki čvor tačke jednostruko povezane liste od susednih temena tog temena. U ovom predstavljanju, čvorovi na jednostruko povezanoj listi mogu se tumačiti kao ivice objekata. Međutim, oni ne sadrže potpune informacije o svakoj ivici (oni samo skladište jednu od dve krajnje tačke na ivici) i u neusmerenim grafovima će biti povezane dve različite povezane liste čvorova za svaku ivicu (jedan u listama za svaki od dve krajnje tačke ivice ).
Objektno orijentisano incidentna lista struktura predložena od Goodrich-a i Tamassia imaju posebne klase čvorova objekata i objekata ivice. Svaki čvor objekat ima promenljivu koja pokazuje na kolekciju objekata koji su navedeni u susedne ivice objekta. Zauzvrat, svaka ivica objekata ukazuje na dva temena objekta na njenim krajnjim tačkama.^[3] Ova verzija liste susedstva koristi više memorije od verzije u kojoj susedna temena su direktno navedena, ali postojanje jasnih ivica objekata omogućava dodatnu fleksibilnost u skladištenje dodatne informacije o ivicama.

Operacije uredi

Glavni operacija koju obavlja struktura podataka liste susedstva je da prijavi listu suseda datog temena. Koristeći bilo koju od implementacija prethodno opisanih, ovo se može izvesti u stalnom vreme po susedima. Drugim rečima ,ukupno vreme izveštavaja za sve susede jednog temena v je proporcionalno stepenu v.

Takođe je mogćue, ali ne tako efikasno, da se koriste liste susedstva za testiranje da li ivica postoji ili ne postoji između dva navedena temena. U listi susedstva u kojoj su nesortirani susedi svakog čvora, testiranje za postojanje ivice se može izvršiti za vreme proporcionalno stepenu jednog od dva datih temena, pomoću sekvencijalne pretrage kroz susede ovog čvora. Ako su komšije predstavljeni kao sortirani niz, binarno pretraživanje može da se koristi, uzimanje vremena proporcionalnog logaritmu stepena.

Alternativa uredi

Glavna alternativa listi susedstva je matrica susedstva, matrica čiji redovi i kolone indeksiraju temena i čije ćelije sadrže Boolean vrednost koja označavaju da li je ivica prisutna između temena koji odgovaraju redu i koloni ćelije. Za oskudan grafa (u kojem većina parova temena nisu povezani ivicama) lista susedstva je znatno više prostorno efikasnija nego matrice susedstva (predstavljena kao niz). Upotreba prostora za listu susedstva je proporcionalan broju ivica i temena u grafu, dok za matricu susedstva skladištene na ovaj način je proporcionalno kvadratu broja temena. Međutim, moguće je da se više prostora - efikasnije skladištiti matrica susedstva tj. da odgovara linearnom korišćenju prostora jedne liste susedstva, korišćenjem heš tabele registrovane u parovima temena.

Drugi značajna razlika između listi susedstva i matrica susedstva je u efikasnosti operacija koje obavljaju. U listi susedstva, komšije svakog temena se mogu efikasno ispisati, u vremenu proporcionalnom stepenu temena. U matrici susedstva, za ovu operaciju potrebno vreme proporcionalno je broju temena u grafu, koji može biti znatno veći od stepena. S druge strane, matrica susedstva dozvoljava testiranje da li dva temena su jedan pored drugog u stalnom vremenu. Lista susedstva je sporija kod ove operacije.

Strukture podataka uredi

Za upotrebu kao strukturu podataka ,glavna alternativa matrice susedstva je lista susedstva. Jer svaki unos u matrici susedstva zahteva samo jedan bit, može biti predstavljena u vrlo kompaktnom obliku , zauzima samo $|V|^{2}/8$ bajtova prostora. Pored izbegavanja izgubljenog prostora, ovo kompaktnost podstiče lokalitet reference.

Međutim, za oskudan grafa, liste susedstva zahtevaju manje prostora za skladištenje , jer ne gubimo prostor da predstavljamo ivice koje nisu prisutne. Korišćenje naivne implementacije niza na 32 - bitnom računaru ,spisak susedstva na neusmerenom grafa zahteva oko $8|E|$ bajtova .

Konstatujući da jednostavni graf može imati najviše $|V|^{2}$ ivice, omogućavajući petlje, možemo reći da $d=|E|/|V|^{2}$ označava gustinu grafa. Zatim , $8|E|>|V|^{2}/8$ , odnosno predstavljanje liste susedstva zauzima više prostora upravo kada $d>1/64$ . Tako da graf mora biti redak da bi zaista opravdao koriščenje liste susedstva.

Pored prostora kompromisu, različite strukture podataka i olakšati različite operacije. Pronalaženje svih temena, susedna temena do datog u vidu listi susedstva je jednostavno kao čitanje liste. Sa susedstva matrice, ceo red mora umesto toga biti skeniran, koji traje $O(|V|)$ vremena. Da li postoji ivica između dve datih temena mogu da se odrede ođednom sa matricom susedstva, a potrebno vreme proporcionalno minimalnom stepenu dva temena sa listom susedstva.

Reference uredi

^ 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. str. 527—529of section 22.1: Representations of graphs. ISBN 978-0-262-03293-3. Nepoznati parametar |auhtorlink= ignorisan (pomoć)
^ Goodrich, Michael T.; Roberto Tamassia (2002). Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. ISBN 978-0-471-38365-9.

Literatura uredi

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. str. 527—529of section 22.1: Representations of graphs. ISBN 978-0-262-03293-3. Nepoznati parametar |auhtorlink= ignorisan (pomoć)

Dodatno za čitanje uredi

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

Spoljašnje veze uredi

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. str. 527—529of section 22.1: Representations of graphs. ISBN 978-0-262-03293-3. Nepoznati parametar |auhtorlink= ignorisan (pomoć)

[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]