Hej alle.
I denne note har jeg besluttet at opremse de vigtigste datastrukturer, der anvendes til opbevaring af grafer i datalogi, samt at fortælle om et par andre strukturer, som på en eller anden måde har 'krystalliseret' sig for mig.
Så lad os komme i gang. Men ikke fra begyndelsen – jeg tænker, at vi allerede ved, hvad en graf er, og hvilke typer der findes (rettede, urettede, vægtede, uvægtede, med flere kanter og løkker eller uden).
Så lad os komme i gang. Hvilke muligheder har vi for datastrukturer til 'grafopbevaring'?
1. Matrixdatastrukturer
1.1 Nabo-matrix. Nabo-matrix repræsenterer en matrix, hvor overskrifterne på rækkerne og kolonnerne svarer til nummerne på grafens hjørner, og værdien af hvert element a(i,j) bestemmes af tilstedeværelsen eller fraværet af kanter mellem hjørnerne i og j (det er klart, at for en urettet graf vil en sådan matrix være symmetrisk, eller man kan blive enige om, at vi kun opbevarer værdierne over hoveddiagonalen). For uvægtede grafer kan a(i,j) angives som antallet af kanter fra i til j (hvis der ikke er en sådan kant, så a(i,j) = 0), og for vægtede grafer også – som vægten (den samlede vægt) af de nævnte kanter.
1.2 Incidensmatrix. I dette tilfælde gemmes vores graf også i en tabel, hvor rækkerne vanligvis svarer til nummerne på dens hjørner, og kolonnerne – til forudnummererede kanter. Hvis et hjørne og en kant er incedente over for hinanden, skrives der en ikke-null værdi i den tilsvarende celle (for urettede grafer skrives 1, hvis der er incidens mellem hjørnet og kanten; for rettede skrives '1', hvis kanten 'går ud' fra hjørnet, og '-1', hvis den 'går ind' i det (det er let at huske, da minus-tegnet også 'går ind' i tallet '-1')). For vægtede grafer kan man igen angive den samlede vægt af kanten i stedet for 1 og -1.
2. Enumerative datastrukturer
2.1 Nabo-liste. Her ser det ud til at være ganske enkelt. Hver toppunkt i grafen kan i almindelighed sættes i forhold til en hvilken som helst opregningsstruktur (liste, vektor, array, …), hvor alle numre på nabotoppunkter gemmes. For rettede grafer vil vi kun tilføje de toppunkter til en sådan liste, som der er en "rettet" kant til fra signaltoppunktet. For vægtede grafer vil implementeringen være mere kompleks.
2.2 Kantliste. En forholdsvis populær datastruktur. Kantlisten, som det åbenlyst hedder, repræsenterer faktisk selve listen af kanter i grafen, hvor hver enkelt kant defineres ved starttoppunktet, sluttoppunktet (for urettede grafer er rækkefølgen ikke vigtig, selvom man for ensartethed kan anvende forskellige regler, fx angive toppunkterne i stigende rækkefølge) og vægten (kun for vægtede grafer).
Man kan se nærmere på de ovennævnte liste-matrixer (og med illustrationer), blandt andet .
2.3 Nabo-array. Ikke den mest almindelige struktur. I sin essens repræsenterer det en form for "pakning" af nabolister i en enkelt opregningsstruktur (array, vektor). De første n (i antal toppunkter i grafen) elementer i et sådant array indeholder startindekserne for det samme array, hvorfra alle nabotoppunkter for det givne punkt sequentialt er indført.
Her fandt jeg den mest forståelige (for mig) forklaring:
3. Nabo-vektor og Associativt nabo-array
Det viste sig, at forfatteren af disse linjer, som ikke er en professionel programmerer, men af og til har haft med grafer at gøre, oftest har arbejdet med kantlister. Uden tvivl, det er bekvemt, når der er flere sløjfer og kanter i grafen. Og da jeg taler om de klassiske kantlister, foreslår jeg at fokusere på deres "udvikling\/afgrening\/modifikation\/mutation", nemlig: nabo-vektoren og det associative nabo-array.
3.1 Nabo-vektor
Sagsforskning (a1): ikke-vægtet graf
Vi vil kalde en nabo-vektor for en ikke-vægtet graf en ordnet samling af et lige antal heltal (a[2i], a[2i+1],…, hvor i nummereres fra 0), hvor hvert par tal a[2i], a[2i+1] angiver en kant i grafen mellem toppunkterne a[2i] og a[2i+1] respektivt.
Denne notationsformat indeholder ikke oplysninger om, hvorvidt grafen er rettet (begge muligheder er mulige). Når formatet anvendes til en graf, betragtes det som om kanten går fra a[2i] til a[2i+1]. Her og fremover: for urettede grafer kan der, hvis nødvendigt, anvendes krav til rækkefølgen af notationen af de hjørner (f.eks. for at den med mindre tildelt nummer kommer først).
I C++ er det hensigtsmæssigt at definere tilstødende vektorer ved hjælp af std::vector, og deraf blev navnet på denne datastruktur valgt.
Situationen (a2): uvejet graf, vægte af kanter er heltal
På samme måde som i situationen (a1) kaldes et tilstødende vektor for en vægtet graf med heltalsvægte et ordnet sæt (dynamisk array) af tal (a[3i], a[3i+1], a[3i+2],…, hvor i nummereres fra 0), hvor hver "triplet" af tal a[3i], a[3i+1], a[3i+2] angiver en kant i grafen mellem hjørnerne med numrene a[3i] og a[3i+1], mens værdien a[3i+2] er vægten af denne kant. En sådan graf kan også være både rettet og urettet.
Situationen (b): uvejet graf, vægte af kanter er ikke heltal
Da det ikke er muligt at gemme heterogene elementer i et enkelt array (vektor), kan den følgende implementering være en mulighed. Grafen gemmes i et par vektorer, hvor den første vektor er grafens tilstødende vektor uden angivelse af vægte, mens den anden vektor indeholder de tilsvarende vægte (en mulig implementering for C++: std::pair). Dermed, for en kant, der angives af parret af hjørner med indekserne 2i, 2i+1 i den første vektor, vil vægten være lig med elementet på indekset i i den anden vektor.
Hvorfor er det nødvendigt?
For forfatteren af disse linjer virkede det til at løse en række opgaver tilstrækkeligt nyttigt. Set fra et formelt synspunkt vil der være sådanne fordele:
- Tilstødende vektorer, ligesom enhver anden "opregnings" struktur, er ret kompakte, optager mindre hukommelse end en tilstødende matrix (for spredte grafer) og er relativt enkle at implementere.
- Grafens hjørner kan i princippet mærkes med negative tal. Måske er der brug for en sådan "afvigelse".
- Grafer kan indeholde flere kanter og flere selvsløjfer, endda med forskellige vægte (positive, negative, endda nul). Der er ingen begrænsninger her.
- Og de kan også have forskellige egenskaber – men se venligst punkt 4.
Men man må erkende, at denne "liste" ikke giver hurtig adgang til en kant. Og her kommer Associativt tilknyttede array til hjælp, som beskrevet nedenfor.
3.2 Associativt tilknyttede array
Så hvis adgang til en bestemt kant, dens vægt og andre egenskaber er kritisk for os, og hukommelseskravene ikke tillader brug af en tilknyttet matrix, lad os da overveje, hvordan vi kan ændre den tilknyttede vektor for at løse dette problem. Nøglen er dermed kanten i grafen, som kan angives som et ordnet par af hele tal. Hvad minder det om? Er det ikke en nøgle i det associative array? Og hvis det er tilfældet, hvorfor så ikke implementere det? Lad os have et sådant associative array, hvor hver nøgle – det ordnede par af hele tal – tildeles en værdi – et helt eller reelt tal, der angiver kantens vægt. I C++ er det hensigtsmæssigt at implementere denne struktur baseret på containeren std::map (std::map <std::pair , int> eller std::map <std::pair , double>), eller std::multimap, hvis der forventes flere kanter. Nå, nu har vi en struktur til lagring af grafer, der bruger mindre hukommelse end "matrix"-strukturer, kan definere grafer med flere sløjfer og kanter, og har endda ingen strenge krav til ikke-negativitet for vertexnumre (jeg ved ikke, hvem der har brug for det, men alligevel).
4. Datatyper er der lige meget, men noget mangler
Og sandt nok: når vi løser flere opgaver, kan vi have brug for at tildele nogle egenskaber til grafens kanter og dermed gemme dem. Hvis det er muligt klart at reducere disse egenskaber til hele tal, kan sådanne "grafer med ekstra egenskaber" gemmes ved hjælp af udvidede versioner af den tilknyttede vektor og det associative tilknyttede array.
Lad os antage, at vi har en uvejet graf, hvor hver kant skal gemme for eksempel 2 yderligere egenskaber repræsenteret ved heltal. I dette tilfælde kan vi definere dens forbindelse som en ordnet samling af ikke "par", men "kvartetter" af heltal (a[2i], a[2i+1], a[2i+2], a[2i+3]...), hvor a[2i+2] og a[2i+3] bestemmer egenskaberne for den tilsvarende kant. For en graf med heltalsvægte for kanterne er rækkefølgen stort set den samme (forskellen vil kun være, at egenskaberne følger efter vægten af kanten og repræsenteres ved elementerne a[2i+3] og a[2i+4], og selve kanten vil blive defineret af 5 ordnede tal i stedet for 4). Og for en graf med ikke-heltalsvægte kan egenskaberne registreres i dens uvejede komponent.
Ved brug af et associativt array til grafer med heltalsvægte kan værdien angives som ikke et enkelt tal, men som et array (vektor) af tal, der angiver, ud over vægten af kanten, alle dens øvrige nødvendige egenskaber. En ulempe ved tilfældet med ikke-heltalsvægte vil være nødvendigheden af at angive egenskaben ved hjælp af et flydende decimalnummer (ja, det er en ulempe, men hvis der ikke er så mange af disse egenskaber, og hvis de ikke skal angives som for "snedige" double-værdier, så er det måske ikke så slemt). Og dermed kan udvidede associative arrays i C++ defineres på følgende måde: std::map <std::pair , std::vector> eller std::map <std::pair , std::vector>, hvor det første element i "vektor-værdien-til-nøglen" vil være vægten af kanten, og derefter kommer de numeriske betegnelser af dens egenskaber.
Litteratur:
Om grafer og algoritmer generelt:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmer: konstruktion og analyse, 2. udgave: Oversat fra engelsk. – Moskva: Forlag "Williams", 2011.
2. Harari, Frank. Grafteori. Moskva: Mir, 1973.
Forfatterens rapport om denne vektor og det associative array til tilslutning:
3. Черноухов С.А. Vektoren af naboskaber og assoziative kort som måder at repræsentere og opbevare grafer på / S.A. Chernouhov. Adjacency vector and adjacency map as data structures to represent a graph // Samling af artikler fra den internationale videnskabelige-praktiske konference "Problemer med implementering af resultaterne fra innovative udviklinger og veje til deres løsning" (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, s. 65-69
Nyttige internetsider om emnet:
4.
5.
Kilde: habr.com
