Pozdrav.
U ovoj bilješci odlučio sam navesti glavne podatkovne strukture koje se koriste za pohranu 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 što je graf i što su (usmjereni, neusmjereni, ponderirani, neponderirani, sa ili bez više rubova i petlji).
Pa, idemo. Koje opcije za strukture podataka za "pohranu grafova" imamo?
1. Matrične strukture podataka
1.1 Matrica susjedstva. Matrica susjedstva je matrica u kojoj zaglavlja redaka i stupaca odgovaraju brojevima vrhova grafa, a vrijednost svakog od njegovih elemenata a(i,j) određena je prisutnošću 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 dogovoriti da sve vrijednosti pohranjujemo samo iznad glavne dijagonale). Za neponderirane grafove, a(i,j) se može postaviti brojem bridova od i do j (ako ne postoji takav rub, onda je a(i,j)= 0), a za ponderirane grafove, također težinom (ukupna težina) navedenih rubova.
1.2 Matrica incidencije. U ovom slučaju, naš graf je također pohranjen u tablici u kojoj, u pravilu, brojevi redaka odgovaraju brojevima njegovih vrhova, a brojevi stupaca odgovaraju unaprijed numeriranim bridovima. Ako su vrh i rub incidentni jedan s drugim, tada se u odgovarajuću ćeliju piše vrijednost koja nije nula (za neusmjerene grafove, 1 se piše ako su vrh i rub incidentni, za usmjerene 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 ponderirane grafove, opet, umjesto 1 i -1, možete odrediti ukupnu težinu ruba.
2. Strukture podataka nabrajanja
2.1 Popis susjedstva. Pa, čini se da je sve jednostavno ovdje. Svaki vrh grafa može se, općenito, pridružiti bilo kojoj enumeracijskoj strukturi (popis, vektor, niz, ...), koja će pohraniti brojeve svih vrhova susjednih zadanom. Za usmjerene grafove, dodat ćemo na takav popis samo one vrhove na koje postoji "usmjereni" brid iz vrha obilježja. Za ponderirane grafove implementacija će biti složenija.
2.2 Popis rebara. Prilično popularna struktura podataka. Popis bridova, kao što nam kaže Captain Obviousness, zapravo je popis bridova grafa, od kojih je svaki određen početnim vrhom, završnim vrhom (za neusmjerene grafove redoslijed ovdje nije bitan, iako za unificiranje možete koristiti razna pravila, na primjer, određivanje vrhova u rastućem redoslijedu) i težinu (samo za ponderirane grafove).
Gore navedene popise matrica možete pogledati detaljnije (i s ilustracijama), na primjer, .
2.3 Niz susjedstva. Nije najčešća struktura. U svojoj srži, to je oblik "pakiranja" popisa susjedstva u jednu enumeracijsku strukturu (niz, vektor). Prvih n (prema broju vrhova grafa) elemenata takvog niza sadrže početne indekse istog niza, počevši od kojih se redom upisuju svi vrhovi susjedni zadanom.
Ovdje sam našao najrazumljivije (za sebe) objašnjenje:
3. Vektor susjedstva i niz asocijativnog susjedstva
Pokazalo se da se autor ovih redaka, budući da nije profesionalni programer, ali se povremeno bavio grafovima, najčešće bavio listama rubova. Doista, zgodno je ako graf ima više petlji i bridova. I tako, u razvoju klasičnih popisa rubova, predlažem da obratite pozornost na njihov "razvoj/grananje/modifikacije/mutacije", naime: vektor susjedstva i asocijativni niz susjedstva.
3.1 Vektor susjedstva
Slučaj (a1): neponderirani graf
Nazvat ćemo vektor susjedstva za neponderirani graf uređeni skup parnog broja cijelih brojeva (a[2i], a[2i+1],..., gdje je i numeriran c 0), u kojem svaki par brojeva je a[2i], a[2i+1 ] specificira rub grafa između vrhova a[2i] i a[2i+1], redom.
Ovaj format snimanja ne sadrži informacije o tome je li graf usmjeren (moguće su obje opcije). Kada se koristi format digrafa, smatra se da je rub usmjeren od a[2i] do a[2i+1]. Ovdje i dolje: za neusmjerene grafove, ako je potrebno, mogu se primijeniti zahtjevi za redoslijed bilježenja vrhova (na primjer, da vrh s nižom vrijednošću broja koji mu je dodijeljen bude prvi).
U C++-u, preporučljivo je navesti vektor susjedstva koristeći std::vector, otuda i naziv ove strukture podataka.
Slučaj (a2): neponderirani graf, težine rubova su cijeli brojevi
Analogno slučaju (a1), vektor susjedstva za ponderirani graf s cjelobrojnim težinama rubova nazivamo uređenim skupom (dinamičkim nizom) brojeva (a[3i], a[3i+1], a[3i+2], ..., gdje je i označen brojem c 0), gdje svaka "trojka" brojeva a[3i], a[3i+1], a[3i+2] specificira rub grafa između vrhova označenih brojem a[3i] odnosno a[3i+1], a vrijednost a [3i+2] je težina ovog ruba. Takav graf također može biti usmjeren ili ne.
Slučaj (b): neponderirani graf, necijelobrojne težine rubova
Budući da je nemoguće pohraniti heterogene elemente u jedan niz (vektor), na primjer, moguća je sljedeća implementacija. Graf je pohranjen u paru vektora, u kojem je prvi vektor susjedni vektor grafa bez navođenja težina, a drugi vektor sadrži odgovarajuće težine (moguća implementacija za C++: std::pair ). Dakle, za brid definiran parom vrhova pod indeksima 2i, 2i+1 prvog vektora, težina će biti jednaka elementu pod indeksom i drugog vektora.
Pa, zašto je to potrebno?
Pa autoru ovih redaka to je bilo vrlo korisno za rješavanje niza problema. Pa, s formalne točke gledišta, bit će sljedeće prednosti:
- Vektor susjedstva, kao i svaka druga "pobrojiva" struktura, prilično je kompaktan, zauzima manje memorije od matrice susjedstva (za rijetke grafove) i relativno ga je lako implementirati.
- Vrhovi grafa, u načelu, mogu se označavati i negativnim brojevima. Što ako je takva "perverzija" potrebna?
- Grafovi mogu sadržavati više rubova i višestruke petlje, 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.
No, mora se priznati da ovaj “popis” ne podrazumijeva brz pristup rubu. I ovdje Associative Adjacency Array dolazi u pomoć, o čemu se govori u nastavku.
3.2 Asocijativni niz susjedstva
Dakle, ako je pristup određenom rubu, njegovoj težini i drugim svojstvima kritičan za nas, a zahtjevi za memorijom nam ne dopuštaju korištenje matrice susjedstva, onda razmislimo o tome kako možemo promijeniti vektor susjedstva da riješimo ovaj problem. Dakle, ključ je rub grafa, koji se može specificirati kao uređeni par cijelih brojeva. Kako ovo izgleda? Nije li to ključ u asocijativnom nizu? I, ako je tako, zašto to ne implementiramo? Neka imamo asocijativni niz gdje će svaki ključ - uređeni par cijelih brojeva - biti pridružen vrijednosti - cijelom broju ili realnom broju koji specificira težinu ruba. U C++-u je preporučljivo implementirati ovu strukturu na temelju spremnika std::map (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šestrukim petljama i rubovima, a čak nema stroge zahtjeve za nenegativnost brojeva vrhova (ne znam kome ovo treba, ali ipak).
4. Strukture podataka su pune, ali nešto nedostaje
I to je istina: prilikom rješavanja brojnih problema, možda ćemo morati dodijeliti neke karakteristike rubovima grafa i, u skladu s tim, pohraniti ih. Ako je moguće nedvosmisleno svesti ove značajke na cijele brojeve, tada je moguće pohraniti takve "grafove s dodatnim značajkama" koristeći proširene verzije vektora susjedstva i asocijativnog niza susjedstva.
Dakle, neka imamo neponderirani graf, za svaki rub kojeg je potrebno pohraniti, na primjer, 2 dodatne značajke određene 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]…) , gdje će a[2i+2] i a[2i+3] odrediti karakteristike odgovarajućeg ruba. Za graf s cjelobrojnim težinama rubova, redoslijed je općenito sličan (jedina će razlika biti u tome što će atributi pratiti težinu ruba i bit će navedeni elementima a[2i+3] i a[2i+4] , a na samom rubu neće biti navedeno 4, već 5 poredanih brojeva). A za graf s težinama rubova koji nisu cijeli brojevi, značajke se mogu zapisati u neponderiranu komponentu.
Kada koristite niz asocijativnih susjedstava za grafove s cjelobrojnim težinama rubova, moguće je specificirati kao vrijednost ne jedan broj, već niz (vektor) brojeva koji određuju, osim težine ruba, sve ostale potrebne značajke. U isto vrijeme, neugodnost za slučaj necijelobrojnih težina bit će potreba za određivanjem znaka s brojem s pomičnim zarezom (da, to je neugodnost, ali ako nema toliko takvih znakova i ako ne Nemojte ih postavljati previše “škakljivo” dvostruko, onda može biti ništa) . To znači da se u C++ prošireni asocijativni nizovi susjedstva mogu definirati na sljedeći način: std::map , std::vector> ili std::map , std::vector, u kojem će prva vrijednost u “key-value-vectoru” biti težina ruba, a zatim se nalaze numeričke oznake njegovih karakteristika.
reference:
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. s 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 susjedstava:
3. Chernoukhov S.A. Vektor susjedstva i asocijativni niz susjedstva kao načini predstavljanja i pohranjivanja grafova / SA Chernouhov. Vektor susjedstva i mapa susjedstva kao strukture podataka za predstavljanje grafa // Zbornik članaka Međunarodne znanstvene i praktične konferencije „Problemi implementacije rezultata inovativnih razvoja i načini njihova rješavanja” (Saratov, 14.09.2019. rujna 2019.). – Sterlitamak: AMI, 65, str. 69-XNUMX (prikaz, ostalo).
Korisni online izvori na temu:
4.
5.
Izvor: www.habr.com