Hei alle sammen.
I dette notatet bestemte jeg meg for å liste opp de viktigste datastrukturene som brukes til å lagre grafer i informatikk, og jeg vil også snakke om et par flere slike strukturer som på en eller annen måte "krystalliserte" for meg.
Så la oss begynne. Men ikke helt fra begynnelsen - jeg tror vi alle allerede vet hva en graf er og hva de er (rettet, urettet, vektet, uvektet, med eller uten flere kanter og løkker).
Så la oss gå. Hvilke alternativer for datastrukturer for "graflagring" har vi?
1. Matrisedatastrukturer
1.1 Adjacency matrise. Adjacency-matrisen er en matrise der rad- og kolonneoverskriftene tilsvarer tallene til toppunktene i grafen, og verdien av hvert av elementene a(i,j) bestemmes av tilstedeværelsen eller fraværet av kanter mellom toppunktene i og j (det er klart at for en urettet graf vil en slik matrise være symmetrisk, eller vi kan bli enige om at vi lagrer alle verdier bare over hoveddiagonalen). For uvektede grafer kan a(i,j) settes med antall kanter fra i til j (hvis det ikke er en slik kant, så a(i,j)= 0), og for vektede grafer også med vekten (total vekt) av de nevnte kantene.
1.2 Forekomstmatrise. I dette tilfellet er grafen vår også lagret i en tabell der radnumrene som regel tilsvarer tallene på hjørnene, og kolonnenumrene tilsvarer forhåndsnummererte kanter. Hvis et toppunkt og en kant faller inn i hverandre, skrives en verdi som ikke er null i den tilsvarende cellen (for urettede grafer skrives 1 hvis toppunktet og kanten faller inn, for orienterte grafer - "1" hvis kanten "utgår" fra toppunktet og "-1" hvis det "inkluderer" i det (det er lett nok å huske, fordi "minus"-tegnet også ser ut til å være "inkludert" i tallet "-1")). For vektede grafer, igjen, i stedet for 1 og -1, kan du spesifisere den totale vekten av kanten.
2. Oppregningsdatastrukturer
2.1 Tilknytningsliste. Vel, alt ser ut til å være enkelt her. Hvert toppunkt i grafen kan generelt assosieres med en hvilken som helst oppregningsstruktur (liste, vektor, matrise, ...), som vil lagre tallene til alle toppunktene ved siden av den gitte. For rettet grafer vil vi legge til en slik liste bare de toppunktene som det er en "rettet" kant til fra et funksjonspunkt. For vektede grafer vil implementeringen være mer kompleks.
2.2 Liste over ribber. Ganske populær datastruktur. Listen over kanter, som Captain Obviousness forteller oss, er faktisk en liste over kanter på grafen, som hver er spesifisert av startpunktet, sluttpunktet (for urettede grafer er rekkefølgen ikke viktig her, selv om du kan bruk ulike regler, for eksempel spesifisere toppunktene i rekkefølge økende) og vekt (kun for vektede grafer).
Du kan se mer detaljert på matriselistene ovenfor (og med illustrasjoner), for eksempel, .
2.3 Adjacency array. Ikke den vanligste strukturen. I kjernen er det en form for å "pakke" tilstøtende lister i én oppregningsstruktur (matrise, vektor). De første n-elementene (i henhold til antall toppunkter i grafen) i en slik matrise inneholder startindeksene til den samme matrisen, fra hvilken alle toppunktene ved siden av den gitte er skrevet på rad.
Her fant jeg den mest forståelige (for meg selv) forklaringen:
3. Adjacency Vector og Associative Adjacency Array
Det viste seg at forfatteren av disse linjene, som ikke var en profesjonell programmerer, men som med jevne mellomrom jobbet med grafer, oftest handlet med lister over kanter. Det er faktisk praktisk hvis grafen har flere løkker og kanter. Og så, i utviklingen av de klassiske listene over kanter, foreslår jeg å ta hensyn til deres "utvikling/gren/modifikasjon/mutasjon", nemlig: tilstøtningsvektoren og den assosiative tilstøtende matrisen.
3.1 Adjacency vektor
Tilfelle (a1): uvektet graf
Vi vil kalle en tilstøtende vektor for en uvektet graf et ordnet sett med et partall av heltall (a[2i], a[2i+1],..., hvor i er nummerert c 0), der hvert par tall er a[2i], angir a[2i+1 ] en grafkant mellom hjørnene a[2i] og a[2i+1], henholdsvis.
Dette opptaksformatet inneholder ikke informasjon om hvorvidt grafen er rettet (begge alternativer er mulige). Når du bruker digrafformatet, anses kanten å være rettet fra a[2i] til a[2i+1]. Her og nedenfor: for urettede grafer, om nødvendig, kan krav til rekkefølgen på registreringspunktene brukes (for eksempel at toppunktet med den laveste verdien av tallet som er tildelt det kommer først).
I C++ er det tilrådelig å spesifisere en tilstøtende vektor ved å bruke std::vector, derav navnet på denne datastrukturen.
Tilfelle (a2): uvektet graf, kantvekter er heltall
I analogi med tilfelle (a1), kaller vi tilstøtningsvektoren for en vektet graf med heltallskantvekter for et ordnet sett (dynamisk matrise) med tall (a[3i], a[3i+1], a[3i+2], ..., hvor i er nummerert c 0), hvor hver "triplett" av tallene a[3i], a[3i+1], a[3i+2] spesifiserer en kant på grafen mellom toppunktene nummerert a[3i] og a[3i+1], henholdsvis, og verdien a [3i+2] er vekten av denne kanten. En slik graf kan også enten være rettet eller ikke.
Tilfelle (b): uvektet graf, kantvekter uten heltall
Siden det er umulig å lagre heterogene elementer i en matrise (vektor), for eksempel, er følgende implementering mulig. Grafen er lagret i et par vektorer, der den første vektoren er grafens tilstøtende vektor uten å spesifisere vektene, og den andre vektoren inneholder de tilsvarende vektene (mulig implementering for C++: std::pair ). Således, for en kant definert av et par toppunkter under indeksene 2i, 2i+1 til den første vektoren, vil vekten være lik elementet under indeksen i til den andre vektoren.
Vel, hvorfor er dette nødvendig?
Vel, forfatteren av disse linjene fant det ganske nyttig for å løse en rekke problemer. Vel, fra et formelt synspunkt vil det være følgende fordeler:
- Adjacency-vektoren, som enhver annen "oppregningsstruktur", er ganske kompakt, tar opp mindre minne enn tilgrensningsmatrisen (for sparsomme grafer), og er relativt enkel å implementere.
- Toppunktene på grafen kan i prinsippet også merkes med negative tall. Hva om en slik "perversjon" er nødvendig?
- Grafer kan inneholde flere kanter og flere løkker, med forskjellig vekt (positiv, negativ, til og med null). Det er ingen begrensninger her.
- Du kan også tilordne ulike egenskaper til kanter - men for mer om det, se avsnitt 4.
Imidlertid må det innrømmes at denne "listen" ikke innebærer rask tilgang til kanten. Og her kommer Associative Adjacency Array til unnsetning, som diskuteres nedenfor.
3.2 Assosiativ tilstøtningsarray
Så hvis tilgang til en spesifikk kant, dens vekt og andre egenskaper er kritiske for oss, og minnekravene ikke tillater oss å bruke tilstøtningsmatrisen, så la oss tenke på hvordan vi kan endre tilstøtningsvektoren for å løse dette problemet. Så nøkkelen er en kant av grafen, som kan spesifiseres som et ordnet par med heltall. Hvordan ser dette ut? Er det ikke en nøkkel i en assosiativ array? Og i så fall, hvorfor implementerer vi det ikke? La oss ha en assosiativ matrise der hver nøkkel - et ordnet par med heltall - vil være assosiert med en verdi - et heltall eller et reelt tall som spesifiserer vekten av kanten. I C++ er det tilrådelig å implementere denne strukturen basert på std::map-beholderen (std::map , int> eller std::map , double>), eller std::multimap hvis det forventes flere kanter. Vel, vi har en struktur for lagring av grafer som tar opp mindre minne enn "matrise" strukturer, kan definere grafer med flere løkker og kanter, og som ikke engang har strenge krav til ikke-negativiteten til toppunkttall (jeg vet ikke hvem trenger dette, men likevel).
4. Datastrukturer er fulle, men noe mangler
Og det er sant: når vi løser en rekke problemer, må vi kanskje tilordne noen egenskaper til kantene på grafen og følgelig lagre dem. Hvis det er mulig å entydig redusere disse funksjonene til heltall, er det mulig å lagre slike "grafer med tilleggsfunksjoner" ved å bruke utvidede versjoner av tilstøtningsvektoren og assosiativ tilstøtende array.
Så la oss ha en uvektet graf, for hver kant det er nødvendig å lagre, for eksempel, 2 ekstra funksjoner spesifisert av heltall. I dette tilfellet er det mulig å definere dens tilstøtende vektor som et ordnet sett ikke av "par", men av "kvartetter" av heltall (a[2i], a[2i+1], a[2i+2], a [2i+3]...) , hvor a[2i+2] og a[2i+3] vil bestemme egenskapene til den tilsvarende kanten. For en graf med heltallsvekter av kanter er rekkefølgen generelt lik (den eneste forskjellen vil være at attributtene vil følge kantens vekt og spesifiseres av elementene a[2i+3] og a[2i+4] , og selve kanten vil ikke spesifiseres 4, men 5 ordnede tall). Og for en graf med kantvekter som ikke er heltall, kan funksjonene skrives inn i den uvektede komponenten.
Når du bruker en assosiativ tilstøtende matrise for grafer med heltallskantvekter, er det mulig å spesifisere som en verdi ikke et enkelt tall, men en matrise (vektor) av tall som spesifiserer, i tillegg til vekten av en kant, alle dens andre nødvendige egenskaper. Samtidig vil en ulempe for ikke-heltallsvekter være behovet for å spesifisere et skilt med et flyttall (ja, dette er en ulempe, men hvis det ikke er så mange slike tegn, og hvis du ikke Ikke sett dem for "vanskelige" dobbelt, da kan det hende det ikke er noe). Dette betyr at i C++ kan utvidede assosiative tilstøtende matriser defineres som følger: std::map , std::vector> eller std::map , std::vector, der den første verdien i "nøkkelverdi-vektoren" vil være vekten av kanten, og deretter er de numeriske betegnelsene for dens egenskaper plassert.
referanser:
Om grafer og algoritmer generelt:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmer: konstruksjon og analyse, 2. utgave: Trans. fra engelsk – M.: Williams Publishing House, 2011.
2. Harari Frank. Grafteori. M.: Mir, 1973.
Forfatterens rapport om disse samme vektorene og assosiative tilknytningene:
3. Chernoukhov S.A. Adjacency vektor og assosiativ adjacency array som måter å representere og lagre grafer / SA Chernouhov. Adjacency vektor og adjacency map som datastrukturer for å representere en graf // Samling av artikler fra International Scientific and Practical Conference “Problems of implement the results of innovative developments and ways to solve them” (Saratov, 14.09.2019. september 2019). – Sterlitamak: AMI, 65, s. 69-XNUMX
Nyttige nettkilder om emnet:
4.
5.
Kilde: www.habr.com