Hallo allemaal.
In deze notitie heb ik besloten om de belangrijkste gegevensstructuren op te sommen die worden gebruikt voor het opslaan van grafen in de informatica, en ik zal ook vertellen over een paar van zulke structuren die vanzelfsprekend 'uitgekristalliseerd' zijn.
Laten we beginnen. Maar niet vanaf het begin – ik denk dat we allemaal al weten wat een graaf is en welke soorten er zijn (gericht, ongericht, gewogen, ongeweight, met meerdere randen en lussen of zonder).
Dus, laten we gaan. Wat zijn de opties voor gegevensstructuren voor 'grafopslag' die we hebben?
1. Matrixgegevensstructuren
1.1 Adjacency matrix. Een adjacente matrix is een matrix waarin de rijen- en kolomkoppen overeenkomen met de nummers van de grafknoten, en de waarde van elk element a(i,j) wordt bepaald door de aanwezigheid of afwezigheid van randen tussen de knopen i en j (het is duidelijk dat voor een ongerichte graaf deze matrix symmetrisch zal zijn, of we kunnen overeenkomen dat we alle waarden alleen boven de hoofddiagonaal opslaan). Voor ongewogen grafen kan a(i,j) worden gedefinieerd door het aantal randen van i naar j (als er geen rand is, dan is a(i,j) = 0), en voor gewogen grafen ook door het gewicht (totaal gewicht) van de genoemde randen.
1.2 Incidentiematrix. In dit geval wordt onze graaf ook opgeslagen in een tabel, waarin gewoonlijk de rij-nummers overeenkomen met de nummers van zijn knopen, en de kolom-nummers met vooraf genummerde randen. Als een knoop en een rand incident zijn aan elkaar, wordt in de bijbehorende cel een niet-nul waarde opgeslagen (voor ongerichte grafen wordt 1 opgeslagen in het geval van incidentie van de knoop en de rand; voor gerichte grafen wordt '1' opgeslagen als de rand 'uit' de knoop komt, en '-1' als deze 'in' de knoop gaat (het is gemakkelijk te onthouden, want het teken 'min' gaat ook 'deze' in het getal '-1')). Voor gewogen grafen kunnen opnieuw in plaats van 1 en -1 de totale gewicht van de rand worden aangegeven.
2. Enumeratieve gegevensstructuren
2.1 Lijst van buren. Nou, het lijkt hier vrij eenvoudig. Aan elke knoop van de grafen kan in het algemeen een willekeurige opsommingstructuur (lijst, vector, array, …) worden toegewezen waarin de nummers van alle knopen die aan deze knoop zijn verbonden, worden opgeslagen. Voor gerichte grafen zullen we in zo'n lijst alleen die knopen opnemen waar een 'gerichte' rand van de aanwijsknoop naartoe gaat. Voor gewogen grafen zal de implementatie complexer zijn.
2.2 Lijst van randen. Een vrij populaire datastructuur. De lijst van randen, zoals ons Captain Obvious vertelt, is simpelweg een lijst van de randen van de grafen, waarbij elke rand wordt gedefinieerd door de begin- en eindknoop (voor niet-gerichte grafen is de volgorde hier niet belangrijk, hoewel het voor uniformiteit nuttig kan zijn om verschillende regels te gebruiken, bijvoorbeeld de knopen in oplopende volgorde aan te geven) en het gewicht (alleen voor gewogen grafen).
Er is meer te zeggen over de eerder genoemde lijsten-matrix, bijvoorbeeld met illustraties, .
2.3 Aangrenzende array. Geen veelvoorkomende structuur. In wezen is het een vorm van 'verpakking' van aangrenzende lijsten in één opsommingstructuur (array, vector). De eerste n (het aantal knopen in de graf) elementen van deze array bevatten de startindexen van dezelfde array, beginnend vanaf waar alle knopen die aan deze knoop zijn verbonden, opeenvolgend zijn genoteerd.
Hier heb ik de meest begrijpelijke (voor mezelf) uitleg gevonden:
3. Aangrenzende vector en Associatieve aangrenzende array
Het gebeurde zo dat de auteur van deze zinnen, die geen professionele programmeur is, maar soms met grafen heeft gewerkt, meestal te maken had met lijsten van randen. Het is inderdaad handig als er meerdere lussen en randen in de graf zijn. En dus, in de ontwikkeling van klassieke lijsten van randen, stel ik voor om ook aandacht te besteden aan hun 'ontwikkeling/vertakking/modificatie/mutatie', namelijk: de aangrenzende vector en de associatieve aangrenzende array.
3.1 Aangrenzende vector
Geval (a1): niet-gewogen graf
We noemen de aangrenzende vector voor een niet-gewogen graf een geordende set van een even aantal gehele getallen (a[2i], a[2i+1],…, waarbij i begint bij 0), waarin elk paar getallen a[2i], a[2i+1] een rand van de graf tussen de knopen a[2i] en a[2i+1] definieert.
Dit schrijfformaat bevat geen informatie of de graf gericht is (beide opties zijn mogelijk). Bij gebruik van het formaat voor een gerichte graaf wordt aangenomen dat de rand is gericht van a[2i] naar a[2i+1]. Hierna geldt: voor niet-gerichte grafen kunnen indien nodig eisen voor de volgorde van de volgorde van de knooppunten worden toegepast (bijvoorbeeld dat eerst het knooppunt met de laagste toegewezen waarde komt).
In C++ is het zinvol om de adjacentievector te definiëren met behulp van std::vector, hieruit is ook de naam van deze datastructuur voortgekomen.
Geval (a2): niet-gewogen graaf, gewichten van de randen zijn gehele getallen
In overeenstemming met geval (a1) zullen we de adjacentievector voor een gewogen graaf met gehele gewichten van de randen noemen, een geordende reeks (dynamische array) van getallen (a[3i], a[3i+1], a[3i+2],…, waar i begint bij 0), waarbij elk "trio" van getallen a[3i], a[3i+1], a[3i+2] een rand van de graaf definieert tussen knooppunten met de nummers a[3i] en a[3i+1] respectievelijk, terwijl de waarde a[3i+2] het gewicht van deze rand is. Deze graaf kan zowel gericht als niet gericht zijn.
Geval (b): niet-gewogen graaf, gewichten van de randen zijn niet-gehele getallen
Aangezien in één array (vector) geen verschillende elementen kunnen worden opgeslagen, is bijvoorbeeld de volgende implementatie mogelijk. De graaf wordt opgeslagen in een paar vectoren, waarbij de eerste vector de adjacentievector van de graaf is zonder gewichtsaanduidingen, en de tweede vector de bijbehorende gewichten bevat (een mogelijke implementatie voor C++: std::pair). Op deze manier zal voor de rand, gedefinieerd door het paar knooppunten onder de indexen 2i, 2i+1 van de eerste vector, het gewicht gelijk zijn aan het element onder index i van de tweede vector.
Maar waarom is dit nodig?
Nou, voor de auteur van deze regels leek dit nuttig voor het oplossen van een aantal problemen. En vanuit een formeel perspectief zijn er dergelijke voordelen:
- De adjacentievector, net als elke andere "opsomming" structuur, is vrij compact, vereist minder geheugen dan de aanstootgevende matrix (voor spaarzame grafen), en is relatief eenvoudig te implementeren.
- De knooppunten van de graaf kunnen in principe ook met negatieve getallen worden gemarkeerd. Wie weet kan deze "afwijking" ook nodig zijn.
- Grafen kunnen meerdere randen en meerdere lussen bevatten, zelfs met verschillende gewichten (positief, negatief, zelfs nul). Hier zijn geen beperkingen aan verbonden.
- Daarnaast kunnen ribben verschillende eigenschappen worden toegewezen - maar zie par. 4.
Het moet echter worden erkend dat deze 'lijst' geen snelle toegang tot de rib biedt. En hier komt de Associatieve aangrenzende array in het spel, waarover hieronder meer.
3.2 Associatieve aangrenzende array
Als de toegang tot een specifieke rib, het gewicht en andere eigenschappen cruciaal voor ons zijn, en de geheugenvereisten ons niet toestaan om een aangrenzende matrix te gebruiken, laten we dan nadenken over hoe we de aangrenzende vector kunnen aanpassen om dit probleem op te lossen. De sleutel is de rib van de graaf, die kan worden weergegeven als een geordend paar gehele getallen. Waar lijkt dit op? Is het niet de sleutel in de associatieve array? En als dat zo is, waarom zouden we dit dan niet implementeren? Laat ons een associatieve array creëren, waar aan elke sleutel - een geordend paar gehele getallen - een waarde wordt gekoppeld - een geheel of een reëel getal dat het gewicht van de rib aangeeft. In C++ is het zinvol om deze structuur te implementeren op basis van de container std::map (std::map <std::pair , int> of std::map <std::pair , double>), of std::multimap indien meerdere ribben worden voorzien. En zo hebben we een structuur voor het opslaan van grafen die minder geheugen vereist dan 'matrix' structuren, de mogelijkheid biedt om grafen met meerdere lussen en ribben te definiëren en zelfs geen strenge eisen stelt aan de niet-negativiteit van knooppuntnummers (ik weet niet wie dat nodig heeft, maar toch).
4. Gegevensstructuren, ongeacht hoe ze worden gevuld, hebben iets tekort
En het is waar: bij het oplossen van verschillende taken kan het nodig zijn om ribben van de graaf bepaalde kenmerken toe te wijzen en deze, dienovereenkomstig, op te slaan. Als deze kenmerken eenduidig kunnen worden teruggebracht tot gehele getallen, is het mogelijk om dergelijke 'grafen met aanvullende kenmerken' op te slaan met behulp van uitgebreide versies van de aangrenzende vector en de associatieve aangrenzende array.
Laten we zeggen dat we een ongewogen graaf hebben, waarbij voor elke rand bijvoorbeeld 2 extra eigenschappen moeten worden opgeslagen, gedefinieerd door gehele getallen. In dit geval kan de aanliggingsvector worden gedefinieerd als een geordende set van 'kwartetten' gehele getallen (a[2i], a[2i+1], a[2i+2], a[2i+3]…), waarbij a[2i+2] en a[2i+3] de eigenschappen van de desbetreffende rand definiëren. Voor een graaf met gehele gewichten blijft de volgorde in wezen hetzelfde (het enige verschil is dat de eigenschappen na het gewicht van de rand komen en gedefinieerd worden door de elementen a[2i+3] en a[2i+4], en de rand zelf zal worden gedefinieerd door 5 geordende getallen in plaats van 4). Voor een graaf met niet-gehele gewichten kunnen de eigenschappen worden genoteerd in de ongewogen component.
Bij het gebruik van een associatieve aanliggingsarray voor grafen met gehele gewichten is het mogelijk om niet een enkel getal als waarde toe te wijzen, maar een array (vector) van getallen, die naast het gewicht van de rand ook alle andere benodigde eigenschappen definiëren. Een ongemak bij niet-gehele gewichten is de noodzaak om de eigenschap met een drijvend-komma getal op te geven (ja, dit is een ongemak, maar als er niet te veel van dergelijke eigenschappen zijn en als je ze niet te 'slim' ingewikkeld maakt, dan is het misschien te doen). Dus kunnen in C++ uitgebreide associatieve aanliggingsarrays als volgt worden gedefinieerd: std::map <std::pair , std::vector> of std::map <std::pair , std::vector, waarbij de eerste waarde in de 'vector-waarde-voor-sleutel' het gewicht van de rand is, gevolgd door de numerieke aanduidingen van zijn eigenschappen.
Literatuur:
Over grafen en algoritmen in het algemeen:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmen: Ontwikkeling en Analyse, 2e editie: Vert. uit het Engels – Moskou: Uitgeverij 'Williams', 2011.
2. Harari, Frank. Grafentheorie. Moskou: Mir, 1973.
De presentatie van de auteur over de genoemde vector en associatieve aanliggingsarray:
3. Черноухов С.А. Adjacency vector en adjacency map als datastructuren voor het vertegenwoordigen van een graaf // Verzameling artikelen van de Internationale wetenschappelijk-praktische conferentie "Problemen van de implementatie van de resultaten van innovaties en oplossingspaden" (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, pp. 65-69
Handige internetbronnen over dit onderwerp:
4.
5.
Bron: habr.com
