Усім прывітанне.
У гэтай нататцы я вырашыў пералічыць асноўныя структуры дадзеных, якія прымяняюцца для захоўвання графаў у інфарматыцы, а таксама раскажу пра яшчэ пару такіх структур, якія ў мяне неяк само сабой «выкрышталізаваліся».
Такім чынам, пачнем. Але не з самага пачатку - думаю, што такое граф і якія яны бываюць (арыентаваныя, неарыентаваныя, узважаныя, няўзважаныя, з множнымі рэбрамі і завесамі ці без іх), мы ўсё ўжо ведаем.
Такім чынам, паехалі. Якія ж варыянты структур дадзеных для "графахавання" мы маем.
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], a[2i+1],…, дзе i нумаруецца c 0), у якім кожная пара лікаў а[2i], a[2i+1 ] задае рабро графа паміж вяршынямі а[2i] і a[2i+1] адпаведна.
Дадзены фармат запісу не змяшчае звестак, ці з'яўляецца граф арыентаваным (магчымыя абодва варыянты). Пры выкарыстанні фармату для орграфа лічыцца, што рабро накіравана з а[2i] у a[2i+1]. Тут і далей: для неарыентаваных графаў, пры неабходнасці, могуць прымяняцца патрабаванні да парадку запісу вяршыняў (напрыклад, каб першай ішла вяршыня з меншым значэннем прысвоенага ёй нумара).
У C++ вектар сумежнасці мэтазгодна задаваць з дапамогай std::vector, адгэтуль і была абрана назва дадзенай структуры дадзеных.
Выпадак (а2): няўзважаны граф, вагі рэбраў цэлалікавыя
Па аналогіі з выпадкам (а1) назавем вектарам сумежнасці для ўзважанага графа з цэлалікавымі вагамі рэбраў спарадкаваны набор (дынамічны масіў) лікаў (а[3i], a[3i+1], a[3i+2],…, дзе i нумаруецца c 0), дзе кожны «трыплет» лікаў а[3i], a[3i+1], a[3i+2] задае рабро графа паміж вяршынямі пад нумарамі а[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 дадатковыя прыкметы, якія задаюцца цэлымі лікамі. У гэтым выпадку можна задаць яго вектар сумежнасці як спарадкаваны набор не "пар", а "квартэтаў" цэлых лікаў (а[2i], a[2i+1], a[2i+2], a[2i+3]…) , дзе a[2i+2] і a[2i+3] і будуць вызначаць прыкметы адпаведнага рабра. Для графа ж з цэлымі вагамі рэбраў парадак, у цэлым, аналагічны (адрозненнем будзе з'яўляцца толькі тая акалічнасць, што прыкметы будуць вынікаць пасля вагі рабра і задавацца элементамі a[2i+3] і a[2i+4], а само рабро будзе задавацца не чатырма, а пятай спарадкаванымі лікамі). А для графа з нецэлалікавымі вагамі рэбраў прыкметы можна будзе запісаць у яго няўзважаны кампанент.
Пры выкарыстанні асацыятыўнага масіва сумежнасці для графаў з цэлалікавымі вагамі рэбраў магчыма ў якасці значэння задаваць не асобны лік, а масіў (вектар) лікаў, якія задаюць, акрамя вагі рабра, усе яго іншыя неабходныя прыкметы. Пры гэтым нязручнасцю для выпадку немалаважных шаляў будзе з'яўляцца неабходнасць задання прыкметы лікам з якая плавае коскі (так, гэта нязручнасць, але калі такіх прыкмет не так і шмат, і калі не задаваць іх занадта «хітрымі» double, то яно, можа, і нічога) . І значыць, у C++ пашыраныя асацыятыўныя масівы сумежнасці могуць задавацца наступным чынам: std::map , std::vector> ці std::map , std::vector, пры гэтым першым значэннем у «вектары-значэнні-па-ключу» будзе вага рабра, а далей размяшчаюцца лікавыя пазначэнні яго прыкмет.
літаратура:
Пра графы і алгарытмы ўвогуле:
1. Кормэн, Томас Х., Лейзерсан, Чарльз І., Рывест, Рональд Л., Штайн, Кліфард. Алгарытмы: пабудова і аналіз, 2-е выданне: Пер. з англ. - М .: Выдавецкі дом «Вільямс», 2011.
2. Харары Фрэнк. Тэорыя графаў. М.: Мір, 1973.
Даклад аўтара пра гэтыя самыя вектар і асацыятыўны масіў сумежнасці:
3. Чарнавухаў С.А. Вектар сумежнасці і асацыятыўны масіў сумежнасці як спосабы прадстаўлення і захоўвання графаў / SA Chernouhov. Adjacency vector and adjacency map is data structures to represent a graph // Зборнік артыкулаў Міжнароднай навукова-практычнай канферэнцыі «Праблемы ўкаранення вынікаў інавацыйных распрацовак і шляхі іх вырашэння» (Саратаў, 14.09.2019 г.). - Сцерлітамак: АМІ, 2019, с. 65-69
Карысныя інтэрнэт-крыніцы па тэме:
4.
5.
Крыніца: habr.com