Pozdrav svima.
U ovoj napomeni odlučio sam da navedem glavne strukture podataka koje se koriste za pohranjivanje grafova u informatici, a govorit ću i o još par takvih struktura koje su mi se nekako „iskristalizirale“.
Dakle, počnimo. Ali ne od samog početka – mislim da svi već znamo šta je graf i šta su (usmereni, neusmereni, ponderisani, neponderisani, sa ili bez više ivica i petlji).
Pa, idemo. Koje opcije za strukture podataka za “skladištenje grafova” imamo?
1. Matrične strukture podataka
1.1 Matrica susjedstva. Matrica susjedstva je matrica u kojoj naslovi reda i stupaca odgovaraju brojevima vrhova grafa, a vrijednost svakog od njegovih elemenata a(i,j) određena je prisustvom ili odsutnošću rubova između vrhova i i j (jasno je da će za neusmjereni graf takva matrica biti simetrična, ili se možemo složiti da sve vrijednosti pohranjujemo samo iznad glavne dijagonale). Za neponderisane grafove, a(i,j) se može postaviti brojem bridova od i do j (ako ne postoji takva ivica, onda je a(i,j)= 0), a za ponderisane grafove takođe težinom (ukupna težina) navedenih ivica.
1.2 Matrica incidencije. U ovom slučaju, naš graf je također pohranjen u tablici u kojoj, po pravilu, brojevi redova odgovaraju brojevima njegovih vrhova, a brojevi stupaca odgovaraju unaprijed numeriranim rubovima. Ako su vrh i ivica incidentni jedan drugom, tada se u odgovarajuću ćeliju upisuje vrijednost različita od nule (za neusmjerene grafove, 1 se upisuje ako su vrh i rub incidentni, za orijentirane grafove - "1" ako je rub “izlazi” iz vrha i “-1” ako se “uključuje” u njega (dovoljno je lako zapamtiti, jer se čini da je znak “minus” također “uključen” u broj “-1”)). Za ponderisane grafove, opet, umesto 1 i -1, možete odrediti ukupnu težinu ivice.
2. Strukture podataka nabrajanja
2.1 Lista susjedstva. Pa, ovde je sve izgleda jednostavno. Svaki vrh grafa može, općenito, biti pridružen bilo kojoj strukturi nabrajanja (lista, vektor, niz, ...), koja će pohraniti brojeve svih vrhova koji su susjedni datom. Za usmjerene grafove, na takvu listu ćemo dodati samo one vrhove na koje postoji „usmjerena“ ivica iz vrha karakteristike. Za ponderisane grafove implementacija će biti složenija.
2.2 Lista rebara. Prilično popularna struktura podataka. Lista ivica, kako nam kaže Kapetan Očevidnost, je zapravo lista ivica grafa, od kojih je svaki specificiran početnim vrhom, završnim vrhom (za neusmjerene grafove redoslijed ovdje nije važan, iako za unificiranje možete koristite razna pravila, na primjer, specificiranje vrhova u rastućem redoslijedu) i težinu (samo za ponderirane grafove).
Možete pogledati gore navedene matrične liste detaljnije (i sa ilustracijama), na primjer, .
2.3 Niz susjedstva. Nije najčešća struktura. U svojoj srži, to je oblik „pakovanja“ susednih lista u jednu strukturu nabrajanja (niz, vektor). Prvih n (prema broju vrhova grafa) elemenata takvog niza sadrže početne indekse istog niza, počevši od kojih su svi vrhovi susedni datom nizu upisani u red.
Ovdje sam našao najrazumljivije (za sebe) objašnjenje:
3. Vektor susjedstva i niz asocijativnog susjedstva
Ispostavilo se da se autor ovih redova, koji nije bio profesionalni programer, ali se povremeno bavio grafovima, najčešće bavio listama ivica. Zaista, zgodno je ako graf ima više petlji i rubova. I tako, u razvoju klasičnih lista ivica, predlažem da se obrati pažnja na njihov „razvoj/grananje/modifikacija/mutacija“, naime: vektor susjedstva i asocijativni niz susjedstva.
3.1 Vektor susjedstva
Slučaj (a1): neponderisani graf
Vektor susednosti za neponderisani graf nazvaćemo uređenim skupom parnog broja celih brojeva (a[2i], a[2i+1],..., gde je i numerisan c 0), u kojem je svaki par brojeva je a[2i], a[2i+1] specificira ivicu grafa između vrhova a[2i] i a[2i+1], respektivno.
Ovaj format snimanja ne sadrži informacije o tome da li je graf usmjeren (moguće su obje opcije). Kada se koristi format digrafa, smatra se da je ivica usmjerena od a[2i] prema a[2i+1]. Ovdje i ispod: za neusmjerene grafove, ako je potrebno, mogu se primijeniti zahtjevi za redoslijed snimanja vrhova (na primjer, da prvo bude vrh sa nižom vrijednošću broja koji mu je dodijeljen).
U C++, preporučljivo je specificirati vektor susjedstva koristeći std::vector, otuda i naziv ove strukture podataka.
Slučaj (a2): neponderisani graf, težine rubova su cijeli brojevi
Po analogiji sa slučajem (a1), vektor susjedstva za ponderirani graf sa cjelobrojnim težinama rubova nazivamo uređenim skupom (dinamičkim nizom) brojeva (a[3i], a[3i+1], a[3i+2], ..., gdje je i numerisan c 0), gdje svaki “trojnjak” brojeva a[3i], a[3i+1], a[3i+2] specificira rub grafa između vrhova numeriranih a[3i] i a[3i+1], respektivno, a vrijednost a [3i+2] je težina ove ivice. Takav graf također može biti usmjeren ili ne.
Slučaj (b): neponderisani graf, necijelobrojne težine rubova
Pošto je nemoguće pohraniti heterogene elemente u jedan niz (vektor), na primjer, moguća je sljedeća implementacija. Graf je pohranjen u par vektora, u kojem je prvi vektor susjedni vektor grafa bez specificiranja pondera, a drugi vektor sadrži odgovarajuće težine (moguća implementacija za C++: std::pair ). Dakle, za ivicu definisanu parom vrhova pod indeksima 2i, 2i+1 prvog vektora, težina će biti jednaka elementu pod indeksom i drugog vektora.
Pa, zašto je ovo potrebno?
Pa, autor ovih redova ga je smatrao prilično korisnim za rješavanje niza problema. Pa, sa formalne tačke gledišta, postojaće sledeće prednosti:
- Vektor susjedstva, kao i svaka druga "enumerativna" struktura, prilično je kompaktan, zauzima manje memorije od matrice susjedstva (za rijetke grafove) i relativno je lak za implementaciju.
- Vrhovi grafa se u principu mogu označiti i negativnim brojevima. Šta ako je takva “perverzija” potrebna?
- Grafovi mogu sadržavati više rubova i više petlji, s različitim težinama (pozitivnim, negativnim, čak i nula). Ovdje nema ograničenja.
- Također možete dodijeliti različita svojstva rubovima - ali za više o tome pogledajte odjeljak 4.
Međutim, mora se priznati da ova „lista“ ne podrazumijeva brz pristup rubu. I tu u pomoć dolazi niz asocijativnog susjedstva, o čemu se govori u nastavku.
3.2 Asocijativni niz susjedstva
Dakle, ako je pristup određenoj ivici, njenoj težini i drugim svojstvima kritičan za nas, a zahtjevi za memorijom ne dozvoljavaju nam da koristimo matricu susjedstva, onda razmislimo o tome kako možemo promijeniti vektor susjedstva da riješimo ovaj problem. Dakle, ključ je ivica grafa, koja se može specificirati kao uređeni par cijelih brojeva. Kako ovo izgleda? Nije li to ključ u asocijativnom nizu? I, ako jeste, zašto to ne implementiramo? Hajde da imamo asocijativni niz u kojem će svaki ključ - uređeni par cijelih brojeva - biti povezan s vrijednošću - cijelim ili realnim brojem koji specificira težinu ruba. U C++, preporučljivo je implementirati ovu strukturu zasnovanu na std::map kontejneru (std::map , int> ili std::map , double>), ili std::multimap ako se očekuje više rubova. Pa, imamo strukturu za pohranjivanje grafova koja zauzima manje memorije od "matričnih" struktura, može definirati grafove s više petlji i rubova, a čak nema ni stroge zahtjeve za nenegativnost brojeva vrhova (ne znam kome ovo treba, ali ipak).
4. Strukture podataka su pune, ali nešto nedostaje
I istina je: kada rješavamo niz problema, možda ćemo morati dodijeliti neke karakteristike rubovima grafa i, shodno tome, pohraniti ih. Ako je moguće nedvosmisleno svesti ove karakteristike na cijele brojeve, onda je moguće pohraniti takve “grafove s dodatnim karakteristikama” koristeći proširene verzije vektora susjedstva i niza asocijativnih susjednosti.
Dakle, neka imamo neponderisani graf, za čiju ivicu je potrebno pohraniti, na primjer, 2 dodatne karakteristike specificirane cijelim brojevima. U ovom slučaju, moguće je definirati njegov vektor susjedstva kao uređeni skup ne "parova", već "kvarteta" cijelih brojeva (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , pri čemu će a[2i+2] i a[2i+3] odrediti karakteristike odgovarajuće ivice. Za graf sa cjelobrojnim težinama ivica, redoslijed je općenito sličan (jedina razlika će biti u tome što će atributi pratiti težinu ruba i bit će specificirani elementima a[2i+3] i a[2i+4] , a sam rub će biti specificiran ne 4, već 5 uređenih brojeva). A za graf sa necjelobrojnim težinama rubova, karakteristike se mogu upisati u njegovu neponderisanu komponentu.
Kada se koristi niz asocijativnog susjedstva za grafove sa cjelobrojnim težinama rubova, moguće je navesti kao vrijednost ne jedan broj, već niz (vektor) brojeva koji specificiraju, pored težine ruba, sve ostale potrebne karakteristike. U isto vrijeme, neugodnost za slučaj necjelobrojnih pondera bit će potreba da se navede znak s brojem s pomičnim zarezom (da, ovo je neugodnost, ali ako takvih znakova nema toliko i ako ne Nemojte ih postaviti previše "škakljivo" duplo, onda možda neće biti ništa) . To znači da se u C++ prošireni nizovi asocijativnog susjedstva mogu definirati na sljedeći način: std::map , std::vector> ili std::map , std::vector, u kojem će prva vrijednost u vektoru „ključ-vrijednost-vektor“ biti težina ruba, a zatim se nalaze numeričke oznake njegovih karakteristika.
Literatura:
O grafovima i algoritmima općenito:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmi: konstrukcija i analiza, 2. izdanje: Trans. sa engleskog – M.: Izdavačka kuća Williams, 2011.
2. Harari Frank. Teorija grafova. M.: Mir, 1973.
Autorov izvještaj o tim istim vektorima i asocijativnim nizovima susjednosti:
3. Chernoukhov S.A. Vektor susjedstva i asocijativni niz susjedstva kao načini za predstavljanje i pohranjivanje grafova / SA Černouhov. Vektor susjedstva i mapa susjedstva kao strukture podataka za predstavljanje grafa // Zbornik članaka Međunarodne znanstveno-praktične konferencije „Problemi implementacije rezultata inovativnog razvoja i načini njihovog rješavanja“ (Saratov, 14.09.2019. rujna 2019.). – Sterlitamak: AMI, 65, str. 69-XNUMX
Korisni online izvori na ovu temu:
4.
5.
izvor: www.habr.com