Поздрав свима.
У овој белешци одлучио сам да наведем главне структуре података које се користе за складиштење графова у рачунарству, а говорићу и о још пар таквих структура које су ми се некако „искристалисале“.
Дакле, почнимо. Али не од самог почетка – мислим да сви већ знамо шта је граф и шта су (усмерени, неусмерени, пондерисани, непондерисани, са или без више ивица и петљи).
Па идемо. Које опције за структуре података за „складиштење графикона“ имамо?
1. Матричне структуре података
1.1 Матрица суседности. Матрица суседности је матрица у којој наслови редова и колона одговарају бројевима врхова графа, а вредност сваког од његових елемената а(и,ј) одређена је присуством или одсуством ивица између врхова и и ј (јасно је да ће за неусмерени граф таква матрица бити симетрична, или се можемо сложити да све вредности чувамо само изнад главне дијагонале). За непондерисане графове, а(и,ј) се може подесити бројем ивица од и до ј (ако такве ивице нема, онда је а(и,ј)= 0), а за пондерисане графове такође тежином (укупна тежина) наведених ивица.
1.2 Матрица инциденције. У овом случају, наш граф се такође чува у табели у којој, по правилу, бројеви редова одговарају бројевима његових врхова, а бројеви колона одговарају унапред нумерисаним ивицама. Ако су врх и ивица инцидентни један другом, онда се у одговарајућу ћелију уписује вредност различита од нуле (за неусмерене графове, 1 се уписује ако су врх и ивица инцидентни, за оријентисане графове - "1" ако је ивица „излази“ из темена и „-1“ ако се „укључује“ у њега (довољно је лако запамтити, јер се чини да је знак „минус“ такође „укључен“ у број „-1“)). За пондерисане графиконе, опет, уместо 1 и -1, можете одредити укупну тежину ивице.
2. Структуре података набрајања
2.1 Листа суседности. Па, овде је све изгледа једноставно. Сваки врх графа може, генерално, бити повезан са било којом структуром набрајања (листа, вектор, низ, ...), која ће чувати бројеве свих врхова који су суседни датом. За усмерене графове, на такву листу ћемо додати само оне врхове на које постоји „усмерена“ ивица из темена обележја. За пондерисане графиконе имплементација ће бити сложенија.
2.2 Списак ребара. Прилично популарна структура података. Листа ивица, како нам каже Капетан Очигледност, је заправо листа ивица графа, од којих је свака одређена почетним врхом, завршним врхом (за неусмерене графове редослед овде није важан, иако за уједињење можете користите различита правила, на пример, одређујући врхове у растућем редоследу) и тежину (само за пондерисане графове).
Можете погледати горе наведене матричне листе детаљније (и са илустрацијама), нпр. .
2.3 Низ суседности. Није најчешћа структура. У својој сржи, то је облик „паковања“ суседних листа у једну структуру набрајања (низ, вектор). Првих н (према броју врхова графа) елемената таквог низа садрже почетне индексе истог низа, почевши од којих се у ред уписују сви врхови који су суседни датом.
Овде сам нашао најразумљивије (за себе) објашњење:
3. Вектор суседности и низ асоцијативних суседности
Испоставило се да се аутор ових редова, не као професионални програмер, али који се периодично бавио графовима, најчешће бавио листама ивица. Заиста, згодно је ако граф има више петљи и ивица. И тако, у развоју класичних листа ивица, предлажем да се обрати пажња на њихов „развој/гранање/модификација/мутација“, наиме: вектор суседности и асоцијативни низ суседности.
3.1 Вектор суседности
Случај (а1): непондерисан график
Вектор суседности за непондерисани граф назваћемо уређеним скупом парног броја целих бројева (а[2и], а[2и+1],..., где је и нумерисан ц 0), у коме је сваки пар бројева је а[2и], а[2и+1] специфицира ивицу графа између врхова а[2и] и а[2и+1], респективно.
Овај формат снимања не садржи информације о томе да ли је граф усмерен (могуће су обе опције). Када се користи формат диграфа, сматра се да је ивица усмерена од а[2и] ка а[2и+1]. Овде и испод: за неусмерене графове, ако је потребно, могу се применити захтеви за редослед бележења темена (на пример, да прво буде врх са мањом вредношћу броја који му је додељен).
У Ц++, препоручљиво је навести вектор суседности користећи стд::вецтор, отуда и назив ове структуре података.
Случај (а2): непондерисани граф, тежине ивица су цели бројеви
По аналогији са случајем (а1), вектор суседности за пондерисани граф са целобројним тежинама ивица називамо уређеним скупом (динамичким низом) бројева (а[3и], а[3и+1], а[3и+2], ..., где је и нумерисано ц 0), где свака „тројка“ бројева а[3и], а[3и+1], а[3и+2] специфицира ивицу графа између темена нумерисаних а[3и] и а[3и+1], респективно, а вредност а [3и+2] је тежина ове ивице. Такав граф такође може бити усмерен или не.
Случај (б): непондерисани граф, тежине ивица које нису целобројне
Пошто је немогуће складиштити хетерогене елементе у један низ (вектор), на пример, могућа је следећа имплементација. Граф је ускладиштен у пар вектора, у којима је први вектор вектор суседности графа без навођења тежине, а други вектор садржи одговарајуће тежине (могућа имплементација за Ц++: стд::паир ). Дакле, за ивицу дефинисану паром темена под индексима 2и, 2и+1 првог вектора, тежина ће бити једнака елементу под индексом и другог вектора.
Па, зашто је ово потребно?
Па, аутор ових редова га је сматрао прилично корисним за решавање низа проблема. Па, са формалне тачке гледишта, биће следеће предности:
- Вектор суседности, као и свака друга „енумеративна“ структура, прилично је компактан, заузима мање меморије од матрице суседности (за ретке графове) и релативно је лак за имплементацију.
- Темена графа се, у принципу, могу означити и негативним бројевима. Шта ако је потребна таква „перверзија“?
- Графови могу да садрже више ивица и више петљи, са различитим тежинама (позитивним, негативним, чак и нула). Овде нема ограничења.
- Такође можете да доделите различита својства ивицама - али за више о томе погледајте одељак 4.
Међутим, мора се признати да ова „листа“ не подразумева брз приступ ивици. И овде у помоћ долази низ асоцијативног суседства, о чему се говори у наставку.
3.2 Асоцијативни низ суседности
Дакле, ако је приступ одређеној ивици, њеној тежини и другим својствима критичан за нас, а захтеви за меморијом не дозвољавају да користимо матрицу суседности, онда размислимо о томе како можемо да променимо вектор суседности да бисмо решили овај проблем. Дакле, кључ је ивица графа, која се може навести као уређени пар целих бројева. Како ово изгледа? Није ли то кључ у асоцијативном низу? И, ако јесте, зашто то не имплементирамо? Хајде да имамо асоцијативни низ где ће сваки кључ - уређени пар целих бројева - бити повезан са вредношћу - целим или реалним бројем који одређује тежину ивице. У Ц++, препоручљиво је имплементирати ову структуру засновану на стд::мап контејнеру (стд::мап , инт> или стд::мап , доубле>), или стд::мултимап ако се очекује више ивица. Па, имамо структуру за чување графова која заузима мање меморије од „матричних“ структура, може да дефинише графове са више петљи и ивица, а чак нема ни строге захтеве за ненегативност бројева врхова (не знам коме ово треба, али ипак).
4. Структуре података су пуне, али нешто недостаје
И тачно је: када решавамо низ проблема, можда ћемо морати да доделимо неке карактеристике ивицама графа и, сходно томе, да их ускладиштимо. Ако је могуће недвосмислено свести ове карактеристике на целе бројеве, онда је могуће чувати такве „графове са додатним карактеристикама“ користећи проширене верзије вектора суседности и низа асоцијативних суседности.
Дакле, да имамо непондерисан граф, за чију ивицу је потребно ускладиштити, на пример, 2 додатне карактеристике одређене целим бројевима. У овом случају, могуће је дефинисати његов вектор суседности као уређени скуп не „парова“, већ „квартета“ целих бројева (а[2и], а[2и+1], а[2и+2], а [2и+3]…) , где ће а[2и+2] и а[2и+3] одредити карактеристике одговарајуће ивице. За граф са целобројним тежинама ивица, редослед је генерално сличан (једина разлика ће бити у томе што ће атрибути пратити тежину ивице и биће специфицирани елементима а[2и+3] и а[2и+4] , а сама ивица ће бити наведена не 4, већ 5 уређених бројева). А за граф са нецелобројним тежинама ивица, карактеристике се могу уписати у његову непондерисану компоненту.
Када се користи низ асоцијативних суседности за графове са целобројним тежинама ивица, могуће је навести као вредност не један број, већ низ (вектор) бројева који специфицирају, поред тежине ивице, све остале неопходне Карактеристике. Истовремено, непријатност за случај нецелобројних тежина биће потреба да се наведе знак са бројем у покретном зарезу (да, ово је непријатност, али ако таквих знакова нема толико, и ако не Не постављајте их превише „шкакљивим“ дуплим, онда можда неће бити ништа). То значи да се у Ц++ проширени низови асоцијативног суседства могу дефинисати на следећи начин: стд::мап , стд::вецтор> или стд::мап , стд::вецтор, у коме ће прва вредност у вектору „кључ-вредност-вектор” бити тежина ивице, а затим се налазе нумеричке ознаке његових карактеристика.
Литература:
О графиконима и алгоритмима уопште:
1. Цормен, Тхомас Х., Леисерсон, Цхарлес И., Ривест, Роналд Л., Стеин, Цлиффорд. Алгоритми: конструкција и анализа, 2. издање: Прев. из енглеског – М.: Издавачка кућа Виллиамс, 2011.
2. Харари Франк. Теорија графова. М.: Мир, 1973.
Ауторов извештај о овим истим векторима и асоцијативним низом суседности:
3. Цхерноукхов С.А. Вектор суседности и асоцијативни низ суседности као начини за представљање и складиштење графова / СА Черноухов. Вектор суседности и мапа суседности као структуре података за представљање графа // Зборник чланака Међународне научно-практичне конференције „Проблеми имплементације резултата иновативних развоја и начини њиховог решавања“ (Саратов, 14.09.2019. септембар 2019). – Стерлитамак: АМИ, 65, стр. 69-XNUMX
Корисни онлајн извори на ову тему:
4.
5.
Извор: ввв.хабр.цом