Datastrukturer för lagring av grafer: en översikt av befintliga och två "nästan nya"

Hej alla.

I denna anteckning har jag beslutat att lista de viktigaste datastrukturerna som används för att lagra grafer inom datavetenskap, samt att jag även kommer att berätta om ett par andra sådana strukturer som av någon anledning har "kristalliserats" fram för mig.

Så, vi börjar. Men inte från början – jag tror att vi alla redan vet vad en graf är och vilka typer som finns (riktade, oriktade, viktade, oviktade, med multipla kanter och slingor eller utan).

Så, låt oss köra. Vilka alternativ har vi då för datastrukturer för "graflagring"?

1. Matristrukturer

1.1 Närliggande matris. En närliggande matris är en matris där rad- och kolumnrubrikerna motsvarar numren på grafens noder, och värdet för varje element a(i,j) bestäms av närvaron eller frånvaron av kanter mellan noderna i och j (det är uppenbart att för en oriktad graf kommer en sådan matris att vara symmetrisk, eller så kan vi komma överens om att vi endast lagrar värden ovanför huvuddiagonalen). För oviktade grafer kan a(i,j) definieras som antalet kanter från i till j (om det inte finns någon sådan kant, då a(i,j) = 0), och för viktade grafer är det också – vikten (den totala vikten) av de nämnda kanterna.

1.2 Incidensmatris. I detta fall lagras vår graf också i en tabell, där radnumren vanligtvis motsvarar numren på dess noder och kolumnnumren – förnumrerade kanter. Om en nod och en kant är incidenta mot varandra, skrivs ett icke-nollvärde in i den motsvarande cellen (för oriktade grafer skrivs 1 vid incident av noden och kanten; för riktade grafer skrivs "1" om kanten "går ut" från noden och "-1" om den "går in" i den (det är ganska lätt att komma ihåg, eftersom tecknet "minus" också "går in" i numret "-1")). För viktade grafer kan man återigen ange den totala vikten av kanten istället för 1 och -1.

2. Uppräknande datastrukturer

2.1 Närliggande lista. Här verkar det vara ganska enkelt. Till varje toppunkt i grafen kan man i allmänhet koppla en valfri uppräkningsstruktur (lista, vektor, array, ...) där nummer på alla toppunkter som är angränsande till den aktuella samlas. För riktade grafer kommer vi endast att lägga till de toppunkter i en sådan lista för vilka det finns en "riktad" kant från den utvalda toppunkten. För vikta grafer kommer implementeringen att vara mer komplex.

2.2 Lista över kanter. En ganska populär datastruktur. En lista över kanter, som Kapten Upplysning påpekar, utgör faktiskt en lista över grafens kanter, där var och en definieras av en starttoppunkt, en ändtoppunkt (för icke-riktade grafer är ordningen här oviktig, även om man för enhetlighet kan använda olika regler, till exempel ange toppunkterna i stigande ordning) och vikt (endast för vikta grafer).

För mer information om de uppräknade listorna-matriserna kan man titta närmare (och med illustrationer), till exempel ). Ett typiskt exempel på användning:.

2.3 Närliggande array. Inte den vanligaste strukturen. I grunden utgör den en form av "packning" av angränsande listor i en enda uppräkningsstruktur (array, vektor). De första n (enligt antalet toppunkter i grafen) elementen i denna array innehåller startindex för samma array, från vilken alla angränsande toppunkter till den aktuella är listade i följd.

Här hittade jag den mest förståeliga (för mig) förklaringen: ejuo.livejournal.com/4518.html

3. Närliggande vektor och Associativ närliggande array

Det visade sig att författaren till dessa rader, utan att vara en professionell programmerare, dock periodiskt har haft att göra med grafer, oftast har jobbat med kanlistor. Det är verkligen praktiskt om grafen har flera slinga och kanter. Så, i utvecklingen av klassiska kanlistor, vill jag ägna uppmärksamhet åt deras "utveckling/kvistande/modifiering/mutation", nämligen: närliggande vektor och associativ närliggande array.

3.1 Närliggande vektor

Fall (a1): oviktad graf

Vi kommer att kalla en närliggande vektor för en oviktad graf en sorterad uppsättning ett jämnt antal heltal (a[2i], a[2i+1], …, där i numreras från 0), där varje talpar a[2i], a[2i+1] definierar en kant i grafen mellan toppunkterna a[2i] och a[2i+1] respektive.
Detta inspelningsformat innehåller inga uppgifter om huruvida grafen är riktad (båda varianterna är möjliga). När formatet används för en ortograf antas kanten vara riktad från a[2i] till a[2i+1]. Här och framöver: för icke-riktade grafer kan, vid behov, krav på ordning av vertexer tillämpas (till exempel så att vertexen med det lägre tilldelade numret kommer först).

I C++ är det lämpligt att använda std::vector för att definiera närliggande vektorer, därav namnet på denna datatyp.

Fall (a2): icke-vägd graf, kantvikter är heltal

I enlighet med fall (a1) kallas en närliggande vektor för en vägd graf med heltalsvikter en ordnad uppsättning (dynamisk array) av nummer (a[3i], a[3i+1], a[3i+2], …, där i numreras från 0), där varje "triplet" av nummer a[3i], a[3i+1], a[3i+2] anger en kant mellan vertexerna med numren a[3i] och a[3i+1], och värdet a[3i+2] är vikten av denna kant. En sådan graf kan också vara både riktad och icke-riktad.

Fall (b): icke-vägd graf, kantvikter är icke-heltal

Eftersom man inte kan lagra heterogena element i en enda array (vektor) kan det exempelvis finnas följande implementering. Grafen lagras i ett par vektorer, där den första vektorn är en närliggande vektor för grafen utan att ange vikter, och den andra vektorn innehåller motsvarande vikter (möjlig implementering för C++: std::pair). Således, för en kant definierad av vertexpar under indexerna 2i, 2i+1 i den första vektorn, är vikten lika med elementet under index i i den andra vektorn.

Men varför behövs detta?

Nåväl, för författaren av dessa rader verkade detta vara ganska användbart för att lösa en rad problem. Ur ett formellt perspektiv finns det sådana fördelar här:

• En närliggande vektor, precis som vilken annan "uppräkning" struktur som helst, är tillräckligt kompakt, tar mindre minne än en närliggande matris (för glesa grafer), och är relativt enkelt att implementera.
• Vertexer i grafen kan i princip märkas med negativa tal. Kanske kan sådana "avvikelser" behövas.
• Grafer kan innehålla multipla kanter och multipla loopar, även med olika vikter (positiva, negativa, till och med noll). Det finns inga begränsningar här.
• Och ribbor kan också tilldelas olika egenskaper – men se punkt 4.

Det måste erkännas att snabb åtkomst till en kant inte åsyftas av denna "listform". Och här kommer den Associativa samarbetetsmatrisen till hjälp, vilket beskrivs nedan.

3.2 Associativ matris för samband

Så, om åtkomsten till en specifik kant, dess vikt och andra egenskaper är kritiska för oss, och minneskraven inte tillåter användning av en sambandsmatris, låt oss tänka på hur vi kan ändra sambandsvektorn för att lösa detta problem. Så, nyckeln är kanten av grafen, som kan anges som ett ordnat par av hela tal. Vad liknar det här? Är det inte en nyckel i en associativ matris? Om så är fallet, varför inte implementera det? Låt oss ha en sådan associativ matris där varje nyckel – ett ordnat par av hela tal – motsvarar ett värde – ett helt eller flyttal som anger vikten på kanten. I C++ är det rimligt att implementera denna struktur baserat på containern std::map (std::map <std::pair , int> eller std::map <std::pair , double>), eller std::multimap, om flera kanter förväntas. Så här, vi har fått en struktur för att lagra grafer som tar upp mindre minne jämfört med "matrisstrukturer", kan representera grafer med flera loopar och kanter och har inte ens strikta krav på icke-negativitet för vertices nummer (jag vet inte vem som behöver det, men ändå).

4. Datatyper ska vara "fulla" men något saknas

Det är sant: vid lösning av en rad problem kan det uppstå behov av att tilldela grafrör något kännetecken och därmed lagra dem. Om dessa kännetecken entydigt kan reduceras till hela tal, kan sådana "grafer med extra kännetecken" lagras med hjälp av utvidgade versioner av sambandsvektor och associativa sambandsmatriser.

Så, låt oss anta att vi har en oviktad graf, där varje kant måste lagra till exempel 2 ytterligare attribut, angivna med heltal. I det här fallet kan vi definiera dess närhetsvektor som en ordnad uppsättning av inte "par", utan "kvartetter" av heltal (a[2i], a[2i+1], a[2i+2], a[2i+3]…), där a[2i+2] och a[2i+3] kommer att definiera egenskaperna för den aktuella kanten. För en graf med heltalsvikter är ordningen i stort sett densamma (skillnaden kommer att vara att egenskaperna kommer att följa efter kanten vikt och anges av elementen a[2i+3] och a[2i+4], och kanten kommer att definieras av inte 4 utan 5 ordnade heltal). För en graf med icke-heltalsvikter kan egenskaperna skrivas in i dess oviktade komponent.

Vid användning av en associativ närhetsmatris för grafer med heltalsvikter är det möjligt att som värde ange inte ett separat tal, utan en array (vektor) av tal som definierar, utöver kantens vikt, alla dess andra nödvändiga egenskaper. Denna situation innebär dock en nackdel för fallet med icke-heltalsvikter, då det är nödvändigt att ange egenskapen som ett flyttal (ja, detta är en nackdel, men om det inte finns så många sådana egenskaper, och om man inte gör dem för "kluriga" med double, kan det kanske gå bra). Således kan utvidgade associativa närhetsmatriser i C++ definieras som: std::map <std::pair , std::vector> eller std::map <std::pair , std::vector, där det första värdet i "vektorn-värdet-för-nyckeln" kommer att vara vikten för kanten, och därefter anges de numeriska beteckningarna för dess egenskaper.

Litteratur:

Om grafer och algoritmer i allmänhet:

1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmer: Konstruktion och analys, 2:a upplagan: Övers. från engelska – Moskva: Förlagshuset "Williams", 2011.
2. Harari, Frank. Grafteori. Moskva: Mir, 1973.
Författarens rapport om just denna vektor och associativa närhetsmatris:
3. Черноухов S.A. Vektor för närstående och associativ matris som sätt att representera och lagra grafer / S.A. Chernouhov. Närstående vektor och närstående karta som datatyper för att representera en graf // Samling av artiklar från den internationella vetenskapligt-praktiska konferensen "Problem med implementering av resultat från innovativa utvecklingar och vägar för att lösa dem" (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, s. 65-69
Nyttiga internetkällor i ämnet:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

Källa: habr.com