Здраво на сите
Во оваа белешка, решив да ги наведам главните структури на податоци што се користат за складирање на графикони во компјутерската наука, а исто така ќе зборувам за уште неколку такви структури кои некако „кристализираа“ за мене.
Значи, да започнеме. Но, не од самиот почеток - мислам дека сите веќе знаеме што е график и што се тие (насочен, ненасочен, пондериран, непондериран, со или без повеќе рабови и јамки).
Значи, да одиме. Кои опции за структури на податоци за „складирање графикони“ ги имаме?
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): непондериран график
Ќе го наречеме вектор на соседство за непондериран граф, подредено множество од парен број цели броеви (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, па оттука и името на оваа структура на податоци.
Случај (а2): непондериран график, тежините на рабовите се цели броеви
По аналогија со случајот (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] е тежината на овој раб. Таков график може да биде или насочен или не.
Случај (б): непондериран график, тежини на нецелобројни рабови
Бидејќи е невозможно да се складираат хетерогени елементи во една низа (вектор), на пример, можна е следната имплементација. Графикот е зачуван во пар вектори, во кои првиот вектор е векторот на соседството на графикот без да се наведат тежините, а вториот вектор ги содржи соодветните тежини (можна имплементација за C++: std::pair ). Така, за раб дефиниран со пар темиња под индексите 2i, 2i+1 од првиот вектор, тежината ќе биде еднаква на елементот под индекс i на вториот вектор.
Па, зошто е ова потребно?
Па, авторот на овие редови смета дека е доста корисно за решавање на голем број проблеми. Па, од формална гледна точка, ќе ги има следните предности:
- Векторот на соседство, како и секоја друга „нумеративна“ структура, е прилично компактен, зафаќа помалку меморија од матрицата на соседството (за ретки графикони) и е релативно лесен за имплементација.
- Темињата на графикот, во принцип, може да се означат и со негативни броеви. Што ако е потребна таква „перверзија“?
- Графиконите може да содржат повеќе рабови и повеќе јамки, со различни тежини (позитивни, негативни, дури и нула). Овде нема ограничувања.
- Можете исто така да доделите различни својства на рабовите - но за повеќе за тоа, видете го делот 4.
Сепак, мора да се признае дека овој „список“ не подразбира брз пристап до работ. И тука Асоцијативната соседна низа доаѓа на помош, за што се дискутира подолу.
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. Кормен, Томас Х., Лејзерсон, Чарлс И., Ривест, Роналд Л., Стајн, Клифорд. Алгоритми: конструкција и анализа, 2. издание: Транс. од англиски - М.: Издавачка куќа Вилијамс, 2011 година.
2. Харари Френк. Теорија на графикони. М.: Мир, 1973 година.
Извештај на авторот за истите векторски и асоцијативни низи соседства:
3. Черноухов С.А. Вектор на соседство и асоцијативна низа за соседство како начини за претставување и складирање на графикони / СА Черноухов. Вектор на соседство и мапа на соседството како структури на податоци за претставување график // Збирка на написи на Меѓународната научна и практична конференција „Проблеми на имплементација на резултатите од иновативните случувања и начини за нивно решавање“ (Саратов, 14.09.2019 септември 2019 година). – Стерлитамак: АМИ, 65 година, стр. 69-XNUMX
Корисни онлајн извори на оваа тема:
4.
5.
Извор: www.habr.com