Popis susjedstva i matrična reprezentacija grafa
Sarah Chen
Iako izgledaju drugačije, svi vrste grafova mogu se prikazati na sličan način. Općenito postoje dvije vrste prikaza grafikona:
- Matrica susjedstva
- Popis susjedstva
Popis susjedstva
Popis susjedstva sastoji se od povezanih popisa. Svaki vrh se smatra indeksom polja, a svaki element predstavlja povezanu listu. Ove povezane liste sadrže vrhove koji imaju bridove s indeksnim vrhom.
Evo primjera popisa susjedstva:
Recimo da graf sadrži V broj vrhova i E broj bridova.
Općenito, složenost prostora bit će O(V + E).
U najgorem slučaju kompleksnost prostora bit će O(V2) ako je dati graf potpuni graf
Matrica susjedstva
Matrica susjedstva sastoji se od 2D niza. Graf koji ima V broj vrhova, veličina matrice bit će VxV.
Reći, matrix[i][j] = 5. To znači da postoji rub između čvorova i i j gdje je težina 5.
Pogledajmo sljedeći graf i njegovu matricu susjedstva:
Stvorili smo 2D niz koristeći ove korake:
Korak 1) Vrh A ima izravni rub s B, a težina je 5. Dakle, ćelija u retku A i stupcu B bit će ispunjena s 5. Ostatak ćelija u retku A bit će ispunjen s nulom.
Korak 2) Vrhovi B imaju izravni brid 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 nulom jer B nema izlazni brid ni u jednu drugi čvorovi.
Korak 3) Vrhovi C nemaju izravnih bridova s drugim vrhovima. Dakle, red C će biti ispunjen nulama.
Korak 4) Vrh D ima usmjeren brid s A i C.
- Ovdje će ćelija u retku D i stupcu A imati vrijednost 7. Ćelije u retku D i stupcu C imat će vrijednost 2.
- Ostatak ćelija u retku D bit će ispunjen nulama.
Korak 5) Vrhovi E imaju usmjeren brid s B i D. Ćelija u retku E i stupcu B imat će vrijednost 6. Ćelije u retku E i stupcu D imat će vrijednost 3. Ostatak ćelija u retku D bit će ispunjen nulama.
Evo nekoliko točaka koje treba primijetiti:
- Graf nema vlastitih petlji kada je primarna dijagonala matrice susjedstva 0.
- Graf je usmjereni graf ako indeksi (a,b) i (b,a) nemaju istu vrijednost. U suprotnom, Graph je usmjereni graf.
- Graf će biti ponderirani graf ako je vrijednost ćelija veća od 1.
Postoji problem s matricom susjedstva jer zahtijeva kvadratne razmake. Ovdje spremamo rubove koji nisu povezani. Ovi rubovi dodjeljuju prostor u memoriji.
Na primjer, ako imamo graf sa 100 čvorova, tada je potrebno 10 tisuća ćelija da ga pohranimo u RAM. S manje rubova u Graphu, dodjeljivanje tako velike memorije može biti gubitak. Dakle, složenost prostora korištenjem matrice susjedstva bit će O(N2), gdje N znači broj čvorova u grafu.
