Popis susjedstva i matrična reprezentacija grafa
Sarah Chen
⚡ Pametni sažetak
Popis susjednosti i matrični prikaz grafa pohranjuju vrhove i bridove u memoriju, omogućujući algoritmima da prolaze kroz mreže. Popis susjednosti koristi povezane popise po vrhu, dok matrica susjednosti koristi kvadratnu dvodimenzionalnu mrežu.
Iako izgledaju drugačije, svi vrste grafova može se predstaviti na sličan način. Općenito postoje dvije vrste grafičkog prikaza:
- Matrica susjedstva
- Popis susjedstva
Popis susjedstva
Lista susjednosti sastoji se od povezanih lista. Svaki vrh se smatra indeksom polja, a svaki element predstavlja povezanu listu. Ove povezane liste sadrže vrhove koji dijele rub s indeksnim vrhom.
Evo primjera liste susjednosti:
Neka graf sadrži V broj vrhova i E broj bridova. Prostorna složenost liste susjednosti je O(V + E), koji se skalira s brojem stvarnih bridova, a ne sa svakim mogućim parom vrhova.
Složenost prostora u najgorem slučaju postaje O(V²) ako je zadani graf potpun graf, budući da se svaki vrh tada povezuje sa svakim drugim vrhom.
Matrica susjedstva
Matrica susjednosti sastoji se od 2D polja. Za graf s V vrhova, veličina matrice bit će V × V.
Reći matrix[i][j] = 5To znači da postoji rub između čvora i i čvora j gdje je težina 5.
Pogledajmo sljedeći graf i njegovu matricu susjednosti:
Izgradili smo 2D niz koristeći ove korake:
Korak 1) Vrh A ima izravnu granu s vrhom B, a težina je 5. Dakle, ćelija u retku A i stupcu B bit će ispunjena s 5. Ostale ćelije u retku A bit će ispunjene s nulom.
Korak 2) Vrh B ima izravni rub s C, a težina je 4. Dakle, ćelija u retku B i stupcu C bit će ispunjena s 4. Preostale ćelije u retku B bit će ispunjene s nulom, budući da B nema izlaznog ruba prema bilo kojem drugom čvoru.
Korak 3) Vrh C nema izravnih rubova s drugim vrhovima. Dakle, redak C bit će popunjen nulama.
Korak 4) Vrh D ima usmjereni brid s A i C.
- Ćelija u retku D i stupcu A imat će vrijednost 7. Ćelija u retku D i stupcu C imat će vrijednost 2.
- Ostatak ćelija u retku D bit će ispunjen nulama.
Korak 5) Vrh E ima usmjereni brid s B i D. Ćelija u retku E i stupcu B imat će vrijednost 6. Ćelija u retku E i stupcu D imat će vrijednost 3. Ostale ćelije u retku E bit će popunjene nulama.
Evo nekoliko točaka koje treba primijetiti:
- Graf nema vlastitih petlji kada je primarna dijagonala matrice susjednosti jednaka 0.
- Graf je usmjereni graf ako ćelije u točkama (a, b) i (b, a) ne sadrže istu vrijednost. U suprotnom, graf je neusmjeren.
- Graf je ponderirani graf ako je vrijednost bilo koje ćelije veća od 1.
Glavni problem s matricom susjednosti je taj što zahtijeva kvadratni prostor. Čak i rubovi koji ne postoje i dalje alociraju ćelije u memoriji.
Na primjer, ako imamo graf sa 100 čvorova, tada je potrebno 10 000 ćelija za njegovo pohranjivanje. RAMS manjim brojem bridova u grafu, alokacija tako velike memorije može biti rasipna. Stoga je prostorna složenost korištenjem matrice susjednosti O(N²), gdje je N broj čvorova u grafu.
Popis susjednosti u odnosu na matricu susjednosti
Prije odabira reprezentacije, korisno je usporediti oba modela jedan pored drugog kroz operacije koje dominiraju stvarnim opterećenjima grafova:
| OperaANJE | Matrica susjedstva | Popis susjedstva |
|---|---|---|
| Složenost prostora | O(V²) | O(V + E) |
| Dodaj vrh | O(V²) | O (1) |
| Dodajte rub | O (1) | O (1) |
| Uklonite rub | O (1) | O(E) |
| Provjeri postoji li rub (i, j) | O (1) | O (stupanj i) |
| Iteriraj preko susjeda od i | O(V) | O (stupanj i) |
| Najbolje za | Gusti grafovi, česti upiti o rubovima | Rijetki grafovi, zadaci s puno prolaska kroz objekte |
Ukratko, matrica susjednosti pobjeđuje kod pretraživanja rubova u konstantnom vremenu, dok lista susjednosti pobjeđuje kod iteracije memorije i susjeda, zbog čega se algoritmi poput BFS-a, DFS-a i Dijkstre obično uparuju s listama susjednosti.
Prednosti i nedostaci grafičkog prikaza
Svaka reprezentacija nosi svoje nedostatke. Poznavanje snaga i slabosti oba modela pomaže vam da odaberete pravi za problem koji rješavate.
Prednosti matrice susjednosti:
- Upiti o postojanju bridova u konstantnom vremenu O(1) između bilo kojeg para vrhova.
- Fiksno indeksiranje olakšava implementaciju algoritama temeljenih na matricama poput Floyd-Warshallovog algoritma i tranzitivnog zatvaranja.
- Ponderirani rubovi prirodno se uklapaju u jednu matričnu ćeliju.
Nedostaci matrice susjednosti:
- Troši O(V²) memorije kada je graf rijedak.
- Dodavanje novog vrha zahtijeva promjenu veličine cijele matrice.
- Iteriranje preko susjeda jednog vrha traje O(V) čak i kada vrh ima samo nekoliko bridova.
Prednosti liste susjednosti:
- Koristi samo O(V + E) memorije, što je blizu stvarnom broju rubova u rijetkim grafovima.
- Dodavanje novog vrha ili brida je O(1).
- Algoritmi za prolazak kroz sustav poput BFS-a i DFS-a iteriraju susjede u O(stupnju), dajući ukupno vrijeme izvođenja O(V + E).
Nedostaci liste susjednosti:
- Provjera postojanja određenog ruba traje O(stupnjeva) umjesto O(1).
- Lokalnost predmemorije je slabija jer su povezane liste raspršene po memoriji.
- Ponderirani rubovi trebaju prateće polje ili popis parova, što malo komplicira strukturu podataka.
Kada koristiti listu susjednosti u odnosu na matricu susjednosti
Izbor reprezentacije ovisi o gustoći grafa i operacijama koje najčešće izvodite. Koristite ovaj kratki vodič za odabir prave strukture:
- Preferirajte matricu susjednosti kada je graf gust (E je blizu V²), kada se rubovi rijetko mijenjaju i kada vaš algoritam više puta pita „postoji li rub između i i j?“.
- Preferiraj popis susjedstva kada je graf rijedak (E je puno manji od V²), kada skup vrhova ili bridova raste tijekom izvršavanja i kada prolazite kroz graf s BFS-om, DFS-om ili Dijkstrin algoritam za najkraći put.
- Preferirajte miješani model (lista susjednosti plus hash skup bridova) kada vam je potrebna i brza iteracija susjeda i O(1) upiti bridova, nauštrb dodatne memorije.
Moderne biblioteke grafova poput NetworkX-a i igrapha prema zadanim postavkama koriste liste susjednosti jer je većina grafova iz stvarnog svijeta - društvene mreže, cestovne karte, web stranice, ovisnosti paketa - rijetka i opterećena prolaskom kroz njih.
