Здравейте на всички.
В тази бележка реших да изброя основните структури от данни, използвани за съхранение на графи в информатиката, и ще разкажа за още няколко подобни структури, които по някакъв начин "се кристализираха" в мен.
И така, да започнем. Но не от самото начало – мисля, че какво е граф и какви видове съществуват (ориентирани, неориентирани, тежести и безтегловни, с множество ръбове и цикли или без тях), всички ние вече знаем.
И така, да видим. Какви варианти на структури от данни за "графско съхранение" имаме.
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), ще наречем вектор на съседство за теглен граф с цели числа, подреден набор (динамичен масив) от числа (а[3i], a[3i+1], a[3i+2],…, където i се номерира от 0), където всеки "триплет" от числа а[3i], а[3i+1], а[3i+2] задава ребро на графа между върховете с номера а[3i] и а[3i+1], а стойността а[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 , std::vector> или std::map <std::pair , std::vector, при което първото значение в "вектора-стойност-по-ключ" ще бъде теглото на ръба, а след това следват числовите обозначения на неговите признаци.
Литература:
За графите и алгоритмите по принцип:
1. Кормен, Томас Х., Лейзерсон, Чарлз И., Ривест, Роналд Л., Штайн, Клиффорд. Алгоритми: изграждане и анализ, 2-ро издание: Превод от английски. – М.: Издателски дом "Вильямс", 2011.
2. Харари Фрэнк. Теория на графите. М.: Мир, 1973.
Доклад на автора за тези самите вектор и асоциативен масив на съседство:
3. Черноухов С.А. Вектор на съседство и асоциативната карта на съседство като методи за представяне и съхранение на графи \/ S.A. Chernouhov. Вектор на съседство и асоциативна карта на съседство като структури от данни за представяне на граф \/\/ Сборник статии от Международната научно-практическа конференция "Проблеми при внедряването на резултатите от иновационни разработки и пътища за решаване" (Саратов, 14.09.2019 г.). – Стерлитамак: АМИ, 2019, стр. 65-69
Полезни интернет ресурси по темата:
4.
5.
Източник: habr.com
