Hej alla.
I den här anteckningen bestämde jag mig för att lista de viktigaste datastrukturerna som används för att lagra grafer inom datavetenskap, och jag kommer också att prata om ett par fler sådana strukturer som på något sätt "kristalliserade" för mig.
Så, låt oss börja. Men inte från första början - jag tror att vi alla redan vet vad en graf är och vad de är (riktad, oriktad, viktad, oviktad, med eller utan flera kanter och slingor).
Låt oss gå. Vilka alternativ för datastrukturer för "graflagring" har vi?
1. Matrisdatastrukturer
1.1 Adjacency matris. Närliggande matris är en matris där rad- och kolumnrubrikerna motsvarar numren på grafens hörn, och värdet på vart och ett av dess element a(i,j) bestäms av närvaron eller frånvaron av kanter mellan hörn. i och j (det är klart att för en oriktad graf kommer en sådan matris att vara symmetrisk, eller så kan vi komma överens om att vi lagrar alla värden endast ovanför huvuddiagonalen). För oviktade grafer kan a(i,j) ställas in med 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, även med vikten (total vikt) av nämnda kanter.
1.2 Incidensmatris. I det här fallet lagras vår graf också i en tabell där radnumren som regel motsvarar numren på dess hörn och kolumnnumren motsvarar förnumrerade kanter. Om en vertex och en kant faller in i varandra, skrivs ett värde som inte är noll i motsvarande cell (för oriktade grafer skrivs 1 om vertex och kant är infallande, för orienterade - "1" om kanten "utgår" från vertexet och "-1" om det "inkluderar" i det (det är lätt nog att komma ihåg, eftersom "minustecknet" också verkar vara "inkluderat" i talet "-1")). För viktade grafer, återigen, istället för 1 och -1, kan du ange kantens totala vikt.
2. Uppräkningsdatastrukturer
2.1 Närhetslista. Tja, allt verkar vara enkelt här. Varje hörn i grafen kan i allmänhet associeras med vilken uppräkningsstruktur som helst (lista, vektor, array, ...), som kommer att lagra numren för alla hörn som gränsar till den givna. För riktade grafer lägger vi till en sådan lista endast de hörn till vilka det finns en "riktad" kant från en funktionspunkt. För viktade grafer blir implementeringen mer komplex.
2.2 Lista över revben. Ganska populär datastruktur. Listan över kanter, som Captain Obviousness berättar för oss, är faktiskt en lista med kanter på grafen, som var och en specificeras av startpunkten, slutpunkten (för oriktade grafer är ordningen inte viktig här, även om du kan förena använd olika regler, till exempel att specificera hörnen i ordningsföljd ökande) och vikt (endast för viktade grafer).
Du kan titta på matrislistorna ovan mer detaljerat (och med illustrationer), till exempel, .
2.3 Adjacency array. Inte den vanligaste strukturen. I sin kärna är det en form av att "packa" närliggande listor i en uppräkningsstruktur (matris, vektor). De första n (enligt antalet hörn i grafen) element i en sådan array innehåller startindexen för samma array, från vilken alla hörn som gränsar till den givna skrivs i en rad.
Här hittade jag den mest förståeliga (för mig själv) förklaringen:
3. Adjacency Vector och Associative Adjacency Array
Det visade sig att författaren till dessa rader, som inte var en professionell programmerare, men som regelbundet sysslade med grafer, oftast sysslade med listor med kanter. Det är faktiskt bekvämt om grafen har flera slingor och kanter. Och så, i utvecklingen av de klassiska listorna med kanter, föreslår jag att uppmärksamma deras "utveckling/gren/modifiering/mutation", nämligen: adjacensvektorn och den associativa adjacensarrayen.
3.1 Adjacencyvektor
Fall (a1): oviktad graf
Vi kallar en närliggande vektor för en oviktad graf för en ordnad uppsättning av ett jämnt antal heltal (a[2i], a[2i+1],..., där i är numrerat c 0), där varje par av tal är a[2i], anger a[2i+1 ] en grafkant mellan hörnen a[2i] respektive a[2i+1].
Detta inspelningsformat innehåller inte information om huruvida grafen är riktad (båda alternativen är möjliga). När du använder digrafformatet anses kanten vara riktad från a[2i] till a[2i+1]. Här och nedan: för oriktade grafer, om nödvändigt, kan krav på ordningen för registrering av hörn tillämpas (till exempel att vertexet med det lägre värdet av det tilldelade numret kommer först).
I C++ är det tillrådligt att specificera en närliggande vektor med std::vector, därav namnet på denna datastruktur.
Fall (a2): oviktad graf, kantvikter är heltal
I analogi med fall (a1) kallar vi närliggande vektor för en viktad graf med heltalskantvikter för en ordnad uppsättning (dynamisk matris) av tal (a[3i], a[3i+1], a[3i+2], ..., där i är numrerad c 0), där varje "triplett" av siffror a[3i], a[3i+1], a[3i+2] anger en kant på grafen mellan hörn numrerade a[3i] respektive a[3i+1], och värdet a [3i+2] är vikten av denna kant. En sådan graf kan också vara antingen riktad eller inte.
Fall (b): oviktad graf, kantvikter utan heltal
Eftersom det är omöjligt att lagra heterogena element i en array (vektor), till exempel, är följande implementering möjlig. Grafen lagras i ett par vektorer, där den första vektorn är grafens närliggande vektor utan att ange vikterna, och den andra vektorn innehåller motsvarande vikter (möjlig implementering för C++: std::pair ). Således, för en kant som definieras av ett par hörn under index 2i, 2i+1 för den första vektorn, kommer vikten att vara lika med elementet under index i för den andra vektorn.
Tja, varför är detta nödvändigt?
Tja, författaren till dessa rader fann det ganska användbart för att lösa ett antal problem. Tja, från en formell synvinkel kommer det att finnas följande fördelar:
- Adjacency-vektorn, som alla andra "uppräkningsstrukturer", är ganska kompakt, tar upp mindre minne än adjacency-matrisen (för glesa grafer) och är relativt lätt att implementera.
- Grafens hörn kan i princip också markeras med negativa tal. Vad händer om en sådan "perversion" behövs?
- Grafer kan innehålla flera kanter och flera slingor, med olika vikt (positiv, negativ, till och med noll). Det finns inga begränsningar här.
- Du kan också tilldela olika egenskaper till kanter - men för mer om det, se avsnitt 4.
Det måste dock erkännas att denna "lista" inte innebär snabb åtkomst till kanten. Och här kommer Associative Adjacency Array till undsättning, vilket diskuteras nedan.
3.2 Associativ adjacency array
Så om tillgången till en specifik kant, dess vikt och andra egenskaper är avgörande för oss, och minneskraven inte tillåter oss att använda närliggande matris, låt oss fundera på hur vi kan ändra närliggande vektor för att lösa detta problem. Så nyckeln är en kant på grafen, som kan specificeras som ett ordnat par heltal. Hur ser det här ut? Är det inte en nyckel i en associativ array? Och i så fall, varför implementerar vi det inte? Låt oss ha en associativ array där varje nyckel - ett ordnat par av heltal - kommer att associeras med ett värde - ett heltal eller ett reellt tal som anger kantens vikt. I C++ är det tillrådligt att implementera denna struktur baserat på std::map-behållaren (std::map , int> eller std::map , double>), eller std::multimap om flera kanter förväntas. Tja, vi har en struktur för att lagra grafer som tar upp mindre minne än "matris"-strukturer, kan definiera grafer med flera slingor och kanter, och som inte ens har strikta krav på icke-negativitet hos vertextal (jag vet inte vem behöver detta, men ändå).
4. Datastrukturer är fulla, men något saknas
Och det är sant: när vi löser ett antal problem kan vi behöva tilldela några egenskaper till grafens kanter och följaktligen lagra dem. Om det är möjligt att entydigt reducera dessa funktioner till heltal, är det möjligt att lagra sådana "grafer med ytterligare funktioner" med hjälp av utökade versioner av närliggande vektor och associativ närliggande array.
Så låt oss ha en oviktad graf, för varje kant som det är nödvändigt att lagra, till exempel, 2 ytterligare funktioner specificerade av heltal. I det här fallet är det möjligt att definiera dess närliggande vektor som en ordnad uppsättning inte av "par", utan av "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 bestämma egenskaperna för motsvarande kant. För en graf med heltalsvikter av kanter är ordningen generellt sett liknande (den enda skillnaden är att attributen följer kantens vikt och kommer att specificeras av elementen a[2i+3] och a[2i+4] , och själva kanten kommer att anges inte 4, utan 5 ordnade nummer). Och för en graf med kantvikter som inte är heltal, kan funktionerna skrivas in i dess oviktade komponent.
När du använder en associativ närliggande array för grafer med heltalskantvikter är det möjligt att som ett värde inte ange ett enstaka tal, utan en array (vektor) av tal som anger, förutom vikten av en kant, alla dess andra nödvändiga Funktioner. Samtidigt kommer en olägenhet för fallet med icke-heltalsvikter att vara behovet av att ange ett tecken med ett flyttal (ja, detta är en olägenhet, men om det inte finns så många sådana tecken, och om du inte ställ dem inte för "knepiga" dubbelt, då kan det vara ingenting). Detta innebär att i C++ kan utökade associativa närliggande arrayer definieras enligt följande: std::map , std::vector> eller std::map , std::vektor, där det första värdet i "nyckel-värde-vektorn" kommer att vara vikten av kanten, och sedan finns de numeriska beteckningarna för dess egenskaper.
Litteratur:
Om grafer och algoritmer i allmänhet:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmer: konstruktion och analys, 2:a upplagan: Trans. från engelska – M.: Williams Publishing House, 2011.
2. Harari Frank. Grafteori. M.: Mir, 1973.
Författarens rapport om samma vektor och associativa samling av närliggande ämnen:
3. Chernoukhov S.A. Adjacency vektor och associativ adjacency array som sätt att representera och lagra grafer / SA Chernouhov. Adjacency-vektor och adjacency-karta som datastrukturer för att representera en graf // Samling av artiklar från International Scientific and Practical Conference "Problem of implement the results of innovative developments and ways to solve them" (Saratov, 14.09.2019 september 2019). – Sterlitamak: AMI, 65, sid. 69-XNUMX
Användbara onlinekällor om ämnet:
4.
5.
Källa: will.com