Здравейте на всички.
В тази бележка реших да изброя основните структури от данни, използвани за съхраняване на графи в информатиката, и ще спомена и няколко други структури, които по някакъв начин самостоятелно "кристализираха".
И така, да започнем. Но не от самото начало – мисля, че какво е граф и какви видове съществуват (ориентирани, неориентирани, тежести, без тежести, с множество ръбове и цикли или без тях), вече всички знаем.
И така, да видим. Какви варианти на структури от данни за "граф-съхранение" имаме.
1. Матрични структури от данни
1.1 Матрица на съседство. Матрицата на съседство представлява матрица, където заглавията на редовете и колоните съответстват на номера на върховете на графа, а стойността на всеки неин елемент a(i,j) се определя от наличието или отсъствието на ръбове между върховете i и j (ясно е, че за неориентиран граф такова матрица ще бъде симетрична, или пък можем да се договорим, че всички стойности ще се запазват само над главната диагонала). За неореждане графове a(i,j) може да се зададе с общия брой ръбове от i към j (ако такъв ръб не съществува, то a(i,j)= 0), а за тежки също – с теглото (общото тегло) на споменатите ръбове.
1.2 Матрица на инцидентност. В този случай нашият граф също се съхранява в таблица, където, като правило, номера на редовете съответстват на номера на неговите върхове, а номера на колоните – на предварително номерирани ръбове. Ако върха и ръба са инцидентни помежду си, то в съответната клетка се записва ненулева стойност (за неориентираните графи се записва 1 в случай на инцидентност между върха и ръба, за ориентираните – "1", ако ръбът "излиза" от върха и "-1", ако влиза в него (запомня се достатъчно лесно, тъй като знакът "минус" също така "влиза" в числото "-1")). За тежките графи отново вместо 1 и -1 можем да указваме общото тегло на ръба.
2. Перечислителни структури от данни
2.1 Списък на съседство. Тук сякаш всичко е просто. На всяка върха на графа в общия случай може да се съответства с всяка изброителна структура (списък, вектор, масив и т.н.), в която ще се съхраняват номерата на всички върхове, съседни на дадената. За насочени графи ще записваме в такъв списък само тези върхове, в които има "насочено" ребро от върха-признак. При тежестни графи реализацията ще бъде по-сложна.
2.2 Списък на ръбовете. Доста популярна структура от данни. Списъкът на ръбовете, както ни подсказва Капитан Очевидност, представлява самия списък на ръбовете на графа, всеки от които се задава със стартова върха, крайна върха (при неориентирани графи редът на последователността не е важен, въпреки че за унификация могат да се използват различни правила, например, да се указват върховете в нарастващ ред) и тежест (само за тежестни графи).
За изброените по-горе списъци-матрици можете да видите по-подробно (и с илюстрации), например, .
2.3 Масив на съседство. Не най-често срещаната структура. По същество, той представлява форма на "опаковане" на списъците на съседство в една изброителна структура (масив, вектор). Първите n (по броя на върховете на графа) елементи на такъв масив съдържат стартовите индекси на същия масив, от които в него последователно са записани всички върхове, съседни на дадената.
Ето тук намерих най-разбираемото (за мен) обяснение:
3. Вектор на съседство и асоциативен масив на съседство
Станало е така, че авторът на тези редове, не будучи професионален програмист, обаче периодично имал работа с графи, най-често се е занимавал със списъци на ръбовете. Наистина, удобно е, когато в графа има многократни цикли и ръбове. И така, в развитие на класическите списъци на ръбовете, предлагам да обърнем внимание и на тяхното "развитие/отклонение/модификация/мутация", а именно: вектор на съседство и асоциативен масив на съседство.
3.1 Вектор на съседство
Случай (а1): неограничен граф
Ще наричаме вектор на съседство за неограничен граф подреден набор от четен брой цели числа (а[2i], а[2i+1],…, където i се номерира от 0), в който всяка двойка числа а[2i], а[2i+1] задава ръб на графа между върховете а[2i] и а[2i+1] съответно.
Този формат на запис не съдържа информация дали графикът е ориентиран (възможни са и двата варианта). При използване на формата за орграф, се приема, че ръбът е насочен от a[2i] към a[2i+1]. Оттук нататък: за неориентирани графи, при необходимост, могат да се прилагат изисквания за реда на запис на върховете (например, за да се започне с върха с по-малка стойност на зададения номер).
В C++ векторът на съседство е уместно да се зададе с помощта на std::vector, оттук и името на тази структура от данни.
Случай (а2): несиметричен граф, теглата на ръбовете са цели числа.
По аналогия със случай (а1), ще наречем вектор с ръбовете на несиметричен граф с цели числа за тегла подреден набор (динамичен масив) от числа (a[3i], a[3i+1], a[3i+2],…, където i се номерира от 0), където всеки "триплет" числа а[3i], a[3i+1], a[3i+2] задава ръб на графа между върховете с номера а[3i] и а[3i+1], а стойността a[3i+2] е теглото на този ръб. Такъв граф може да бъде както ориентиран, така и неориентиран.
Случай (б): несиметричен граф, теглата на ръбовете не са цели числа.
Тъй като в един масив (вектор) не могат да се съхраняват хетерогенни елементи, е възможна, например, следната реализация. Графът се съхранява в двойка вектори, при което първият вектор е вектор на съседство на графа без указание за теглата, а вторият вектор съдържа съответните тегла (възможна реализация за C++: std::pair). По този начин, за ръб, зададен от двойката върхове под индексите 2i, 2i+1 на първия вектор, теглото ще бъде равно на елемента под индекса i на втория вектор.
Но каква е ползата от това?
Но на автора на тези редове му се струва достатъчно полезно за решаването на редица задачи. А от формална гледна точка, тук ще има следните предимства:
- Векторът на съседство, подобно на всяка друга "перечислителна" структура, е доста компактен, заема по-малко памет в сравнение с матрицата на съседство (за разредени графи) и е относително лесен за реализиране.
- Върховете на графа, принципно, могат да бъдат маркирани и с отрицателни числа. В случай че се наложи и такъв "изврат".
- Графите могат да съдържат множество ръбове и множество цикли, причем с различни тегла (положителни, отрицателни, дори нулеви). Няма ограничения в това отношение.
- Освен това, на ребрата могат да се задават различни свойства – но за това вижте т. 4.
Въпреки това, трябва да признаем, че бърз достъп до реброто не е предвиден в този "списък". И тук на помощ идва асоциативният масив на съседство, за което – по-долу.
3.2 Асосативен масив на съседство
И така, ако достъпът до конкретно ребро, неговото тегло и други свойства е критичен за нас, а изискванията за памет не позволява да се използва матрица на съседство, нека помислим как можем да променим вектора на съседство, за да решим този проблем. Ключът е реброто на графа, което може да бъде зададено като подредена двойка цели числа. Какво ми напомня това? А не е ли ключ в асоциативен масив? А, ако е така, защо да не го реализираме? Нека имаме такъв асоциативен масив, където на всеки ключ – подредена двойка цели числа – се съответства стойност – цяло или действително число, задаващо теглото на реброто. В C++ реализацията на тази структура е целесъобразна на базата на контейнера std::map (std::map <std::pair , int> или std::map <std::pair , double>), или std::multimap, ако се предвиждат множество ребра. И ето, получихме структура за съхранение на графове, която заема по-малко памет в сравнение с "матричните" структури, може да задава графи с множество цикли и ребра и дори не притежава строги изисквания за неотрицателност на номерата на върховете (не знам на кого е нужно това, но все пак).
4. Структури от данни, макар и "да се заливат", нещо не достига
Наистина: при решаване на редица задачи може да се появи необходимост от присвояване на някакви признаци на ребрата на графа и, съответно, в тяхното съхранение. Ако е възможно еднозначно да се сведе тези признаци до цели числа, е възможно да се съхраняват такива "графи с допълнителни признаци", използвайки разширени версии на вектора на съседство и асоциативния масив на съседство.
Така, да предположим, че имаме неориентиран граф, за всеки ръб на който трябва да се съхраняват, например, 2 допълнителни характеристики, определяни от цели числа. В този случай е възможно да зададем неговия вектор на съседство като подреден набор от не „пари“, а „квартети“ цели числа (a[2i], a[2i+1], a[2i+2], a[2i+3]…), където a[2i+2] и a[2i+3] ще определят характеристиките на съответния ръб. За граф с цели тегла на ръбовете, подредбата, по принцип, е аналогична (различието ще бъде, че характеристиките ще следват след теглото на ръба и ще се задават от елементите a[2i+3] и a[2i+4], а самият ръб ще се задава не с 4, а с 5 подредени числа). А за граф с нецелочислени тегла на ръбовете характеристиките могат да бъдат записани в неговия неориентиран компонент.
При използване на асоциативен масив на съседство за графи с цели тегла на ръбовете е възможно като стойност да задавате не отделно число, а масив (вектор) от числа, определящи, освен теглото на ръба, всички негови останали необходими характеристики. Въпреки това, неудобството за случая с нецелочислени тегла ще бъде необходимостта да зададете характеристиката като число с плаваща запетая (да, това е неудобство, но ако такива характеристики не са много и ако не се задават твърде „сложни“ double числа, може би няма да е толкова зле). Следователно, в C++ разширените асоциативни масиви на съседство могат да бъдат зададени по следния начин: std::map <std::pair < int, int>, std::vector> или std::map <std::pair < int, int>, std::vector, като първата стойност в „вектора-стойност-по-ключа“ ще бъде теглото на ръба, а след това ще се разполагат числените обозначения на неговите характеристики.
Литература:
За графите и алгоритмите изобщо:
1. Кормен, Томас Х., Лейзерсон, Чарлз И., Ривест, Роналд Л., Штайн, Клифорд. Алгоритми: построение и анализ, 2-ро издание: Прев. от англ. – М.: Издателски дом „Уилямс“, 2011.
2. Харари Фрънк. Теория на графите. М.: Мир, 1973.
Доклад на автора за тези вектор и асоциативен масив на съседство:
3. Черноухов С.А. Вектор на съседство и асоциативен масив на съседство като методи за представяне и съхранение на графи / S.A. Chernouhov. Вектор на съседство и асоциативна карта на съседство като данни структури за представяне на граф / / Сборник статии на Международната научна и практическа конференция «Проблеми на внедряването на резултатите от иновационните разработки и възможните решения» (Саратов, 14.09.2019 г.). – Стерлитамак: АМИ, 2019, с. 65-69
Полезни интернет източници по темата:
4.
5.
Източник: habr.com
