Hallo allemaal
In deze notitie heb ik besloten de belangrijkste datastructuren op te sommen die worden gebruikt om grafieken in de informatica op te slaan, en ik zal ook praten over nog een paar van dergelijke structuren die op de een of andere manier voor mij zijn "gekristalliseerd".
Dus laten we beginnen. Maar niet vanaf het allereerste begin - ik denk dat we allemaal al weten wat een grafiek is en wat ze zijn (gericht, ongericht, gewogen, ongewogen, met of zonder meerdere randen en lussen).
Dus laten we gaan. Welke opties voor datastructuren voor ‘grafiekopslag’ hebben we?
1. Matrixdatastructuren
1.1 Nabijheidsmatrix. De aangrenzende matrix is een matrix waarbij de rij- en kolomkoppen overeenkomen met de nummers van de hoekpunten van de grafiek, en de waarde van elk van de elementen a(i,j) wordt bepaald door de aanwezigheid of afwezigheid van randen tussen hoekpunten i en j (het is duidelijk dat voor een ongerichte grafiek zo'n matrix symmetrisch zal zijn, of we kunnen afspreken dat we alle waarden alleen boven de hoofddiagonaal opslaan). Voor ongewogen grafieken kan a(i,j) worden ingesteld op basis van het aantal randen van i tot j (als er geen dergelijke rand is, dan is a(i,j)= 0), en voor gewogen grafieken ook op basis van het gewicht (totaalgewicht) van de genoemde randen.
1.2 Incidentiematrix. In dit geval wordt onze grafiek ook opgeslagen in een tabel waarin de rijnummers in de regel overeenkomen met de nummers van de hoekpunten en de kolomnummers met vooraf genummerde randen. Als een hoekpunt en een rand op elkaar invallen, wordt een waarde die niet nul is, in de corresponderende cel geschreven (voor ongerichte grafieken wordt 1 geschreven als het hoekpunt en de rand invallen, voor georiënteerde grafieken - "1" als de rand "verlaat" het hoekpunt en "-1" als het daarin "opneemt" (het is gemakkelijk genoeg om te onthouden, omdat het "min"-teken ook "opgenomen" lijkt te zijn in het getal "-1")). Voor gewogen grafieken kunt u, in plaats van 1 en -1, het totale gewicht van de rand opgeven.
2. Opsommingsdatastructuren
2.1 Nabijheidslijst. Nou, alles lijkt hier eenvoudig te zijn. Elk hoekpunt van de grafiek kan in het algemeen worden geassocieerd met elke opsommingsstructuur (lijst, vector, array, ...), die de nummers van alle hoekpunten naast het gegeven opslaat. Voor gerichte grafieken zullen we aan een dergelijke lijst alleen die hoekpunten toevoegen waaraan een “gerichte” rand van een feature-hoekpunt bestaat. Voor gewogen grafieken zal de implementatie complexer zijn.
2.2 Lijst met ribben. Een behoorlijk populaire datastructuur. De lijst met randen is, zoals Kapitein Obviousness ons vertelt, eigenlijk een lijst met randen van de grafiek, die elk worden gespecificeerd door het beginpunt en het eindpunt (voor ongerichte grafieken is de volgorde hier niet belangrijk, hoewel je dat voor unificatie wel kunt doen). gebruik verschillende regels, bijvoorbeeld door de hoekpunten op te geven in oplopende volgorde) en het gewicht (alleen voor gewogen grafieken).
U kunt de hierboven genoemde matrixlijsten gedetailleerder (en met illustraties) bekijken, bijvoorbeeld: .
2.3 Aangrenzende array. Niet de meest voorkomende structuur. In de kern is het een vorm van het ‘verpakken’ van aangrenzende lijsten in één opsommingsstructuur (array, vector). De eerste n (volgens het aantal hoekpunten van de grafiek) elementen van een dergelijke array bevatten de startindexen van dezelfde array, te beginnen van waaruit alle hoekpunten die grenzen aan de gegeven hoek op een rij worden geschreven.
Hier vond ik de meest begrijpelijke (voor mezelf) uitleg:
3. Aangrenzende vector en associatieve aangrenzende array
Het bleek dat de auteur van deze regels, die geen professionele programmeur was, maar die periodiek met grafieken bezig was, meestal met lijsten met randen te maken had. Het is inderdaad handig als de grafiek meerdere lussen en randen heeft. En dus stel ik voor om bij de ontwikkeling van de klassieke lijsten met randen aandacht te besteden aan hun “ontwikkeling/tak/modificatie/mutatie”, namelijk: de aangrenzende vector en de associatieve aangrenzende array.
3.1 Nabijheidsvector
Geval (a1): ongewogen grafiek
We zullen een aangrenzende vector voor een ongewogen grafiek een geordende set van een even aantal gehele getallen noemen (a[2i], a[2i+1],..., waarbij i genummerd is c 0), waarin elk paar getallen is a[2i], a[2i+1 ] specificeert een grafiekrand tussen respectievelijk de hoekpunten a[2i] en a[2i+1].
Dit opnameformaat bevat geen informatie over of de grafiek gericht is (beide opties zijn mogelijk). Bij gebruik van het digraph-formaat wordt aangenomen dat de rand is gericht van a[2i] naar a[2i+1]. Hier en hieronder: voor ongerichte grafieken kunnen, indien nodig, eisen worden gesteld aan de volgorde van de opnamehoekpunten (bijvoorbeeld dat het hoekpunt met de lagere waarde van het eraan toegewezen getal als eerste komt).
In C++ is het raadzaam om een aangrenzende vector te specificeren met behulp van std::vector, vandaar de naam van deze datastructuur.
Geval (a2): ongewogen grafiek, randgewichten zijn gehele getallen
Naar analogie met geval (a1) noemen we de aangrenzende vector voor een gewogen grafiek met gehele randgewichten een geordende set (dynamische array) van getallen (a[3i], a[3i+1], a[3i+2], ..., waarbij i genummerd is c 0), waarbij elk “triplet” van getallen a[3i], a[3i+1], a[3i+2] een rand van de grafiek specificeert tussen de hoekpunten genummerd a[3i] en a[3i+1], respectievelijk, en de waarde a [3i+2] is het gewicht van deze rand. Zo'n grafiek kan ook gericht zijn of niet.
Geval (b): ongewogen grafiek, niet-gehele randgewichten
Omdat het bijvoorbeeld onmogelijk is om heterogene elementen in één array (vector) op te slaan, is de volgende implementatie mogelijk. De grafiek wordt opgeslagen in een paar vectoren, waarbij de eerste vector de aangrenzende vector van de grafiek is zonder de gewichten te specificeren, en de tweede vector de overeenkomstige gewichten bevat (mogelijke implementatie voor C++: std::pair ). Voor een rand die wordt gedefinieerd door een paar hoekpunten onder de indexen 2i, 2i+1 van de eerste vector, zal het gewicht dus gelijk zijn aan het element onder index i van de tweede vector.
Waarom is dit nodig?
Welnu, de auteur van deze regels vond het behoorlijk nuttig om een aantal problemen op te lossen. Welnu, vanuit formeel oogpunt zijn er de volgende voordelen:
- De aangrenzende vector is, net als elke andere "enumeratieve" structuur, vrij compact, neemt minder geheugen in beslag dan de aangrenzende matrix (voor schaarse grafieken) en is relatief eenvoudig te implementeren.
- De hoekpunten van de grafiek kunnen in principe ook worden gemarkeerd met negatieve getallen. Wat als een dergelijke ‘perversie’ nodig is?
- Grafieken kunnen meerdere randen en meerdere lussen bevatten, met verschillende gewichten (positief, negatief, zelfs nul). Er zijn hier geen beperkingen.
- U kunt ook verschillende eigenschappen aan randen toewijzen, maar voor meer informatie daarover, zie sectie 4.
Er moet echter worden toegegeven dat deze “lijst” geen snelle toegang tot de edge impliceert. En hier komt de Associative Adjacency Array te hulp, die hieronder wordt besproken.
3.2 Associatieve aangrenzende array
Dus als de toegang tot een specifieke rand, het gewicht ervan en andere eigenschappen van cruciaal belang voor ons zijn, en de geheugenvereisten ons niet toelaten de aangrenzende matrix te gebruiken, laten we dan eens nadenken over hoe we de aangrenzende vector kunnen veranderen om dit probleem op te lossen. De sleutel is dus een rand van de grafiek, die kan worden gespecificeerd als een geordend paar gehele getallen. Hoe ziet dit eruit? Is het niet een sleutel in een associatieve array? En zo ja, waarom implementeren we het dan niet? Laten we een associatieve array hebben waarin elke sleutel - een geordend paar gehele getallen - wordt geassocieerd met een waarde - een geheel getal of een reëel getal dat het gewicht van de rand specificeert. In C++ is het raadzaam om deze structuur te implementeren op basis van de std::map container (std::map , int> of std::map , double>), of std::multimap als er meerdere randen worden verwacht. Welnu, we hebben een structuur voor het opslaan van grafieken die minder geheugen in beslag neemt dan “matrix”-structuren, die grafieken kan definiëren met meerdere lussen en randen, en die zelfs geen strikte eisen stelt aan de niet-negativiteit van hoekpunten (ik weet het niet). wie heeft dit nodig, maar toch).
4. Datastructuren zijn vol, maar er ontbreekt iets
En het is waar: bij het oplossen van een aantal problemen moeten we mogelijk enkele kenmerken aan de randen van de grafiek toewijzen en dienovereenkomstig opslaan. Als het mogelijk is om deze kenmerken ondubbelzinnig terug te brengen tot gehele getallen, dan is het mogelijk om dergelijke “grafieken met extra kenmerken” op te slaan met behulp van uitgebreide versies van de aangrenzende vector en de associatieve aangrenzende array.
Laten we dus een ongewogen grafiek hebben, voor elke rand waarvan het bijvoorbeeld nodig is om twee extra kenmerken op te slaan, gespecificeerd door gehele getallen. In dit geval is het mogelijk om de aangrenzende vector te definiëren als een geordende verzameling, niet van “paren”, maar van “kwartetten” van gehele getallen (a[2i], a[2i+2], a[1i+2], a [2i+2]…) , waarbij a[3i+2] en a[2i+2] de kenmerken van de corresponderende rand zullen bepalen. Voor een grafiek met gehele gewichten van randen is de volgorde over het algemeen vergelijkbaar (het enige verschil is het feit dat de attributen het gewicht van de rand zullen volgen en zullen worden gespecificeerd door de elementen a[3i+2] en a[3i+ 2], en de rand zelf zal niet 4, maar 4 geordende nummers worden gespecificeerd). En voor een grafiek met niet-gehele randgewichten kunnen de kenmerken in de ongewogen component worden geschreven.
Wanneer u een associatieve aangrenzende array gebruikt voor grafieken met randgewichten van gehele getallen, is het mogelijk om als waarde niet één enkel getal te specificeren, maar een array (vector) van getallen die, naast het gewicht van een rand, al het andere noodzakelijke specificeren. functies. Tegelijkertijd zal een ongemak voor het geval van niet-gehele gewichten de noodzaak zijn om een teken met een drijvende-kommagetal te specificeren (ja, dit is een ongemak, maar als er niet zo veel van dergelijke tekens zijn, en als je dat niet doet Zet ze niet te “lastig” dubbel, dan kan het niets zijn). Dit betekent dat in C++ uitgebreide associatieve aangrenzende arrays als volgt kunnen worden gedefinieerd: std::map , std::vector> of std::map , std::vector, waarin de eerste waarde in de "sleutelwaarde-vector" het gewicht van de rand zal zijn, en vervolgens de numerieke aanduidingen van de kenmerken ervan.
Literatuur:
Over grafieken en algoritmen in het algemeen:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmen: constructie en analyse, 2e editie: Trans. van Engels – M.: Williams Publishing House, 2011.
2. Harari Frank. Grafentheorie. M.: Mir, 1973.
Het rapport van de auteur over dezelfde vector en associatieve reeks aangrenzende gebieden:
3. Tsjernouchov SA Aangrenzende vector en associatieve aangrenzende array als manieren om grafieken weer te geven en op te slaan / SA Chernouhov. Nabijheidsvector en aangrenzende kaart als datastructuren om een grafiek weer te geven // Verzameling artikelen van de Internationale Wetenschappelijke en Praktische Conferentie “Problemen bij het implementeren van de resultaten van innovatieve ontwikkelingen en manieren om ze op te lossen” (Saratov, 14.09.2019 september 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Nuttige online bronnen over dit onderwerp:
4.
5.
Bron: www.habr.com