Здравейте на всички.
В тази бележка реших да изброя основните структури от данни, използвани за съхраняване на графики в компютърните науки, и също така ще говоря за още няколко такива структури, които по някакъв начин „кристализираха“ за мен.
И така, да започваме. Но не от самото начало - мисля, че всички вече знаем какво е граф и какви са те (насочени, ненасочени, претеглени, непретеглени, със или без множество ребра и цикли).
И така, да вървим. Какви опции за структури от данни за „съхранение на графики“ имаме?
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 Списък на ребрата. Доста популярна структура от данни. Списъкът с ръбове, както ни казва Captain Obviousness, всъщност е списък с ръбове на графа, всеки от които е определен от началния връх, крайния връх (за неориентираните графи редът не е важен тук, въпреки че за обединяване можете използвайте различни правила, например указване на върховете в ред на нарастване) и тегло (само за претеглени графи).
Можете да разгледате списъците с матрици, изброени по-горе, по-подробно (и с илюстрации), например, .
2.3 Съседен масив. Не е най-често срещаната структура. В основата си това е форма на „опаковане“ на списъци със съседство в една изброяваща структура (масив, вектор). Първите n (според броя на върховете на графа) елемента на такъв масив съдържат началните индекси на същия масив, започвайки от които се записват подред всички върхове, съседни на дадения.
Тук намерих най-разбираемото (за себе си) обяснение:
3. Вектор на съседство и масив на асоциативно съседство
Оказа се, че авторът на тези редове, който не е професионален програмист, но периодично се занимава с графики, най-често се занимава със списъци от ребра. Наистина е удобно, ако графиката има множество контури и ръбове. И така, в развитието на класическите списъци с ръбове, предлагам да се обърне внимание на тяхното „развитие/разклонение/модификация/мутация”, а именно: векторът на съседство и асоциативният масив на съседство.
3.1 Вектор на съседство
Случай (a1): непретеглена графика
Ще наречем вектор на съседство за непретеглен график подреден набор от четен брой цели числа (a[2i], a[2i+1],..., където i е номерирано c 0), в който всяка двойка числа е a[2i], a[2i+1] определя ребро на граф между върховете a[2i] и a[2i+1], съответно.
Този формат на запис не съдържа информация дали графиката е насочена (възможни са и двете опции). Когато се използва формат на диграф, ръбът се счита за насочен от a[2i] към a[2i+1]. Тук и по-долу: за неориентираните графи, ако е необходимо, могат да се прилагат изисквания за реда на записване на върховете (например първо да е върхът с по-малка стойност на присвоения му номер).
В C++ е препоръчително да се посочи вектор на съседство чрез std::vector, откъдето идва и името на тази структура от данни.
Случай (a2): непретеглена графика, теглата на ръбовете са цяло число
По аналогия със случай (a1), ние наричаме вектора на съседство за претеглен график с целочислени тегла на ребра подреден набор (динамичен масив) от числа (a[3i], a[3i+1], a[3i+2], ..., където i е номерирано c 0), където всяка „тройка“ от числа a[3i], a[3i+1], a[3i+2] определя ребро на графиката между върхове, номерирани a[3i] и a[3i+1], съответно, а стойността a [3i+2] е теглото на това ребро. Такава графа също може да бъде насочена или не.
Случай (b): непретеглена графика, нецелочислени тегла на ръба
Тъй като е невъзможно да се съхраняват хетерогенни елементи в един масив (вектор), например, е възможна следната реализация. Графиката се съхранява в двойка вектори, в които първият вектор е векторът на съседство на графиката, без да се уточняват теглата, а вторият вектор съдържа съответните тегла (възможна реализация за C++: std::pair ). Така за ребро, дефинирано от двойка върхове под индекси 2i, 2i+1 на първия вектор, теглото ще бъде равно на елемента под индекс i на втория вектор.
Е, защо е необходимо това?
Е, авторът на тези редове я намира за доста полезна за решаването на редица проблеми. Е, от формална гледна точка ще има следните предимства:
- Векторът на съседство, както всяка друга „изброяваща“ структура, е доста компактен, заема по-малко памет от матрицата на съседство (за редки графики) и е сравнително лесен за изпълнение.
- Върховете на графа по принцип също могат да бъдат маркирани с отрицателни числа. Ами ако е необходима такава „перверзия“?
- Графиките могат да съдържат множество ребра и множество цикли с различни тегла (положителни, отрицателни, дори нула). Тук няма ограничения.
- Можете също така да присвоите различни свойства на ръбовете - но за повече информация вижте раздел 4.
Все пак трябва да се признае, че този „списък“ не предполага бърз достъп до ръба. И тук на помощ идва Associative Adjacency Array, който е разгледан по-долу.
3.2 Асоциативен масив на съседство
Така че, ако достъпът до конкретен ръб, неговото тегло и други свойства са критични за нас и изискванията за памет не ни позволяват да използваме матрицата на съседство, тогава нека помислим как можем да променим вектора на съседство, за да разрешим този проблем. И така, ключът е ребро на графиката, което може да бъде определено като подредена двойка цели числа. на какво прилича това Не е ли ключ в асоциативен масив? И ако е така, защо не го приложим? Нека имаме асоциативен масив, където всеки ключ - подредена двойка цели числа - ще бъде свързан със стойност - цяло число или реално число, което определя теглото на ръба. В C++ е препоръчително тази структура да се приложи въз основа на контейнера std::map (std::map , int> или std::map , 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 подредени числа). А за графика с тегла на ребра, които не са цели числа, характеристиките могат да бъдат записани в нейния непретеглен компонент.
Когато се използва асоциативен масив за съседство за графики с целочислени тегла на ребра, е възможно да се посочи като стойност не едно число, а масив (вектор) от числа, които определят, в допълнение към теглото на ребра, всички останали необходими Характеристика. В същото време неудобство за случая на нецелочислени тегла ще бъде необходимостта да посочите знак с число с плаваща запетая (да, това е неудобство, но ако няма толкова много такива знаци и ако не Не ги настройвайте твърде „сложно“ двойно, тогава може да е нищо) . Това означава, че в C++ разширените асоциативни масиви за съседство могат да бъдат дефинирани както следва: std::map , std::vector> или std::map , std::vector, в който първата стойност във “key-value-vector” ще бъде теглото на ръба, а след това са разположени цифровите обозначения на неговите характеристики.
литература:
За графиките и алгоритмите като цяло:
1. Кормен, Томас Х., Лейзерсън, Чарлз I., Ривест, Роналд Л., Стайн, Клифърд. Алгоритми: конструиране и анализ, 2-ро издание: Прев. от английски – М.: Издателство Уилямс, 2011.
2. Харари Франк. Теория на графите. М.: Мир, 1973.
Докладът на автора за същия този вектор и асоциативен масив от съседства:
3. Черноухов С.А. Вектор на съседство и асоциативен масив на съседство като начини за представяне и съхраняване на графи / SA Chernouhov. Вектор на съседство и карта на съседство като структури от данни за представяне на графика // Сборник от статии на Международната научно-практическа конференция „Проблеми на внедряване на резултатите от иновационни разработки и начини за тяхното решаване“ (Саратов, 14.09.2019 септември 2019 г.). – Стерлитамак: АМИ, 65, с. 69-XNUMX
Полезни онлайн източници по темата:
4.
5.
Източник: www.habr.com