Hej alle sammen.
I denne note besluttede jeg at liste de vigtigste datastrukturer, der bruges til at gemme grafer i datalogi, og jeg vil også tale om et par flere sådanne strukturer, der på en eller anden måde "krystalliserede" for mig.
Så lad os begynde. Men ikke helt fra begyndelsen - jeg tror, vi alle allerede ved, hvad en graf er, og hvad de er (rettet, urettet, vægtet, uvægtet, med eller uden flere kanter og sløjfer).
Så lad os gå. Hvilke muligheder for datastrukturer til "graflagring" har vi?
1. Matrix datastrukturer
1.1 Adjacency matrix. Adjacency-matricen er en matrix, hvor række- og kolonneoverskrifterne svarer til numrene på grafens hjørner, og værdien af hvert af dens elementer 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 vi kan blive enige om, at vi kun gemmer alle værdier over hoveddiagonalen). For uvægtede grafer kan a(i,j) indstilles med antallet af kanter fra i til j (hvis der ikke er en sådan kant, så er a(i,j)= 0), og for vægtede grafer også med vægten (totalvægt) af de nævnte kanter.
1.2 Incidensmatrix. I dette tilfælde er vores graf også gemt i en tabel, hvor rækkenumrene som regel svarer til numrene på dens hjørner, og kolonnenumrene svarer til forudnummererede kanter. Hvis et toppunkt og en kant falder ind i forhold til hinanden, skrives en værdi, der ikke er nul, i den tilsvarende celle (for urettede grafer skrives 1, hvis toppunktet og kanten er indfaldende, for orienterede - "1", hvis kanten "udgår" fra toppunktet og "-1", hvis det "inkluderer" i det (det er nemt nok at huske, fordi "minus"-tegnet også ser ud til at være "inkluderet" i tallet "-1")). For vægtede grafer, igen, i stedet for 1 og -1, kan du angive den samlede vægt af kanten.
2. Optællingsdatastrukturer
2.1 Tilgrænsende liste. Nå, alt ser ud til at være enkelt her. Hvert toppunkt på grafen kan generelt være forbundet med en hvilken som helst opregningsstruktur (liste, vektor, array, ...), som vil gemme numrene på alle hjørner, der støder op til den givne. For rettede grafer vil vi kun føje de hjørner til en sådan liste, hvortil der er en "rettet" kant fra et trækpunkt. For vægtede grafer vil implementeringen være mere kompleks.
2.2 Liste over ribben. En ganske populær datastruktur. Listen over kanter, som Captain Obviousness fortæller os, er faktisk en liste over kanter af grafen, som hver især er specificeret af startpunktet, slutpunktet (for urettede grafer er rækkefølgen ikke vigtig her, selvom du kan bruge forskellige regler, for eksempel at specificere toppunkterne i rækkefølge stigende) og vægt (kun for vægtede grafer).
Du kan se mere detaljeret på matrixlisterne ovenfor (og med illustrationer), f.eks. .
2.3 Adjacency array. Ikke den mest almindelige struktur. I sin kerne er det en form for at "pakke" tilgrænsende lister i én opregningsstruktur (array, vektor). De første n (i henhold til antallet af hjørner i grafen) elementer i en sådan matrix indeholder startindeksene for den samme matrix, hvorfra alle hjørner, der støder op til den givne, er skrevet i en række.
Her fandt jeg den mest forståelige (for mig selv) forklaring:
3. Adjacency Vector og Associative Adjacency Array
Det viste sig, at forfatteren af disse linjer, der ikke var en professionel programmør, men som periodisk beskæftigede sig med grafer, oftest beskæftigede sig med lister over kanter. Det er faktisk praktisk, hvis grafen har flere løkker og kanter. Og så, i udviklingen af de klassiske lister over kanter, foreslår jeg at være opmærksom på deres "udvikling/gren/modifikation/mutation", nemlig: adjacency-vektoren og den associative adjacency-array.
3.1 Adjacency vektor
Tilfælde (a1): uvægtet graf
Vi vil kalde en nabovektor for en uvægtet graf for et ordnet sæt af et lige antal heltal (a[2i], a[2i+1],..., hvor i er nummereret c 0), hvor hvert par tal er a[2i], angiver a[2i+1 ] en grafkant mellem hhv. hjørnerne a[2i] og a[2i+1.
Dette optagelsesformat indeholder ikke information om, hvorvidt grafen er rettet (begge muligheder er mulige). Når du bruger digrafformatet, anses kanten for at være rettet fra a[2i] til a[2i+1]. Her og nedenfor: for ikke-rettede grafer, om nødvendigt, kan krav til rækkefølgen af optagelse af toppunkter anvendes (f.eks. at toppunktet med den laveste værdi af det tildelte tal kommer først).
I C++ er det tilrådeligt at angive en tilstødende vektor ved hjælp af std::vector, deraf navnet på denne datastruktur.
Tilfælde (a2): uvægtet graf, kantvægte er heltal
I analogi med tilfælde (a1) kalder vi tilstødende vektor for en vægtet graf med heltal kantvægtning for et ordnet sæt (dynamisk array) af tal (a[3i], a[3i+1], a[3i+2], ..., hvor i er nummereret c 0), hvor hver "triplet" af tallene a[3i], a[3i+1], a[3i+2] angiver en kant på grafen mellem hjørner nummereret a[3i] og a[3i+1], og værdien a [3i+2] er vægten af denne kant. En sådan graf kan også enten være rettet eller ej.
Tilfælde (b): uvægtet graf, kantvægte uden heltal
Da det er umuligt at gemme heterogene elementer i et array (vektor), for eksempel, er følgende implementering mulig. Grafen er gemt i et par vektorer, hvor den første vektor er grafens tilstødende vektor uden at angive vægtene, og den anden vektor indeholder de tilsvarende vægte (mulig implementering for C++: std::pair ). For en kant defineret af et par hjørner under indekserne 2i, 2i+1 af den første vektor, vil vægten således være lig med elementet under indeks i af den anden vektor.
Nå, hvorfor er det nødvendigt?
Nå, forfatteren af disse linjer fandt det ganske nyttigt til at løse en række problemer. Nå, fra et formelt synspunkt vil der være følgende fordele:
- Adjacency-vektoren, som enhver anden "optalende" struktur, er ret kompakt, optager mindre hukommelse end adjacency-matricen (for sparsomme grafer) og er relativt nem at implementere.
- Grafens hjørner kan i princippet også markeres med negative tal. Hvad hvis en sådan "perversion" er nødvendig?
- Grafer kan indeholde flere kanter og flere loops med forskellige vægte (positive, negative, endda nul). Der er ingen begrænsninger her.
- Du kan også tildele forskellige egenskaber til kanter - men for mere om det, se afsnit 4.
Det skal dog indrømmes, at denne "liste" ikke indebærer hurtig adgang til kanten. Og her kommer Associative Adjacency Array til undsætning, som diskuteres nedenfor.
3.2 Associative adjacency array
Så hvis adgang til en specifik kant, dens vægt og andre egenskaber er kritiske for os, og hukommelseskravene ikke tillader os at bruge tilstødende matrix, så lad os tænke på, hvordan vi kan ændre tilstødende vektor for at løse dette problem. Så nøglen er en kant af grafen, som kan specificeres som et ordnet par heltal. Hvordan ser det her ud? Er det ikke en nøgle i et associativt array? Og i så fald, hvorfor implementerer vi det så ikke? Lad os have et associativt array, hvor hver nøgle - et ordnet par heltal - vil være forbundet med en værdi - et heltal eller et reelt tal, der angiver vægten af kanten. I C++ er det tilrådeligt at implementere denne struktur baseret på std::map containeren (std::map , int> eller std::map , double>), eller std::multimap, hvis der forventes flere kanter. Nå, vi har en struktur til lagring af grafer, der optager mindre hukommelse end "matrix"-strukturer, kan definere grafer med flere sløjfer og kanter og ikke engang har strenge krav til ikke-negativitet af topnumre (jeg ved det ikke) hvem har brug for dette, men alligevel).
4. Datastrukturerne er fulde, men der mangler noget
Og det er sandt: Når vi løser en række problemer, skal vi muligvis tildele nogle karakteristika til grafens kanter og følgelig gemme dem. Hvis det er muligt entydigt at reducere disse funktioner til heltal, så er det muligt at gemme sådanne "grafer med yderligere funktioner" ved hjælp af udvidede versioner af tilstødende vektor og associativ tilstødende array.
Så lad os have en uvægtet graf, for hver kant det er nødvendigt at gemme, for eksempel, 2 yderligere funktioner specificeret af heltal. I dette tilfælde er det muligt at definere dens tilstødende vektor som et ordnet sæt, ikke af "par", men af "kvartetter" af heltal (a[2i], a[2i+1], a[2i+2], a [2i+3]...) , hvor a[2i+2] og a[2i+3] vil bestemme karakteristikaene for den tilsvarende kant. For en graf med heltalvægte af kanter er rækkefølgen generelt ens (den eneste forskel vil være, at attributterne vil følge vægten af kanten og vil blive specificeret af elementerne a[2i+3] og a[2i+4] , og selve kanten angives ikke 4, men 5 ordnede numre). Og for en graf med ikke-heltals kantvægte kan funktionerne skrives ind i dens uvægtede komponent.
Når du bruger en associativ tilstødende matrix til grafer med heltal kantvægte, er det muligt at angive som en værdi ikke et enkelt tal, men en matrix (vektor) af tal, der specificerer, udover vægten af en kant, alle dens andre nødvendige funktioner. Samtidig vil en ulempe for tilfælde af ikke-heltalsvægte være behovet for at angive et tegn med et flydende decimaltal (ja, dette er en ulempe, men hvis der ikke er så mange sådanne tegn, og hvis du ikke ikke sæt dem for "tricky" dobbelt, så er det måske ingenting). Dette betyder, at i C++ kan udvidede associative adjacency-arrays defineres som følger: std::map , std::vector> eller std::map , std::vektor, hvor den første værdi i "nøgleværdi-vektoren" vil være vægten af kanten, og derefter er de numeriske betegnelser for dens karakteristika placeret.
Litteratur:
Om grafer og algoritmer generelt:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmer: konstruktion og analyse, 2. udgave: Trans. fra engelsk – M.: Williams Publishing House, 2011.
2. Harari Frank. Grafteori. M.: Mir, 1973.
Forfatterens rapport om disse samme vektorer og associative rækker af tilstødende forbindelser:
3. Chernoukhov S.A. Adjacency vektor og associative adjacency array som måder at repræsentere og gemme grafer / SA Chernouhov. Adjacency-vektor og adjacency-kort som datastrukturer til at repræsentere en graf // Indsamling af artikler fra den internationale videnskabelige og praktiske konference "Problemer med at implementere resultaterne af innovative udviklinger og måder at løse dem på" (Saratov, 14.09.2019. september 2019). – Sterlitamak: AMI, 65, s. 69-XNUMX
Nyttige onlinekilder om emnet:
4.
5.
Kilde: www.habr.com