Moni nonse.
M'mawu awa, ndidaganiza zolembera zidziwitso zazikulu zomwe zimagwiritsidwa ntchito kusungira ma graph mu sayansi yamakompyuta, ndipo ndilankhulanso zamagulu angapo oterowo omwe mwanjira ina "adandipangira" ine.
Kotero, tiyeni tiyambe. Koma osati kuyambira pachiyambi - ndikuganiza kuti tonse tikudziwa kale kuti graph ndi chiyani komanso zomwe zili (zolunjika, zosalongosoka, zolemetsa, zopanda malire, zokhala ndi m'mphepete mwambiri kapena malupu).
Kotero, tiyeni tizipita. Ndi zosankha ziti zamapangidwe a data pa "graph storage" zomwe tili nazo?
1. Zomangamanga za data za matrix
1.1 Matrix oyandikana nawo. Matrix oyandikana ndi matrix pomwe mitu ya mzere ndi mizere imagwirizana ndi manambala a vertices ya graph, ndipo mtengo wa chilichonse mwazinthu zake a(i,j) umatsimikiziridwa ndi kupezeka kapena kusapezeka kwa m'mphepete pakati pa vertices. i ndi j (zikuwonekeratu kuti pa graph yosalunjika matrix oterowo adzakhala ofanana, kapena titha kuvomereza kuti timasunga zikhalidwe zonse pamwamba pa diagonal yayikulu). Kwa ma graph opanda kulemera, a (i, j) akhoza kukhazikitsidwa ndi chiwerengero cha m'mphepete kuchokera ku i mpaka j (ngati palibe malire, ndiye a(i,j)= 0), ndi ma graph olemera, komanso kulemera kwake. (kulemera konse) kwa m'mphepete mwatchulidwa.
1.2 Zochitika matrix. Pankhaniyi, graph yathu imasungidwanso patebulo momwe, monga lamulo, manambala amizere amafanana ndi manambala a vertices ake, ndipo manambala amizere amafanana ndi m'mphepete mwa manambala. Ngati vertex ndi m'mphepete zimachitikira wina ndi mzake, ndiye kuti mtengo wosakhala wa ziro umalembedwa mu selo lofananira (kwa ma graph osadziwika, 1 amalembedwa ngati vertex ndi m'mphepete zikuchitika, kwa ma graph ozungulira - "1" ngati m'mphepete mwake. "kutuluka" kuchokera ku vertex ndi "-1" ngati "kuphatikiza" mmenemo (ndizosavuta kukumbukira, chifukwa chizindikiro cha "minus" chikuwonekanso kuti "chophatikizidwa" mu chiwerengero "-1")). Kwa ma graph olemedwa, kachiwiri, m'malo mwa 1 ndi -1, mutha kufotokozera kulemera konse kwa m'mphepete.
2. Zolemba zowerengera
2.1 Mndandanda woyandikana. Chabwino, chirichonse chikuwoneka chophweka apa. Vertex iliyonse ya graph imatha, makamaka, kulumikizidwa ndi kalembedwe kalikonse (mndandanda, vekitala, gulu, ...), yomwe imasunga manambala a ma vertices onse moyandikana ndi yomwe yaperekedwa. Pazithunzi zowongoleredwa, tidzawonjezera pamndandanda woterewo ma vertices omwe ali ndi "mphepete" kuchokera ku vertex. Kwa ma graph olemetsa kukhazikitsa kudzakhala kovuta kwambiri.
2.2 Mndandanda wa nthiti. Dongosolo lodziwika bwino la data. Mndandanda wa m'mphepete, monga Captain Obviousness amatiuza, kwenikweni ndi mndandanda wa m'mphepete mwa graph, iliyonse yomwe imatchulidwa ndi vertex yoyambira, vertex yotsiriza (kwa ma graph osadziwika dongosolo siliri lofunikira pano, ngakhale kuti kugwirizana mungathe. gwiritsani ntchito malamulo osiyanasiyana, mwachitsanzo, kutchula ma vertices kuti achuluke) ndi kulemera (kwa ma graph olemera okha).
Mutha kuyang'ana pamndandanda wamatrix womwe watchulidwa pamwambapa mwatsatanetsatane (komanso ndi zithunzi), mwachitsanzo, .
2.3 Mzere woyandikana. Osati mapangidwe ambiri. Pachimake, ndi mtundu wa "kulongedza" mindandanda yoyandikana mumtundu umodzi wowerengera (gulu, vector). Yoyamba n (malinga ndi kuchuluka kwa ma vertices a graph) zinthu zamtundu wotere zimakhala ndi zoyambira zamagulu omwewo, kuyambira pomwe ma vertices onse oyandikana ndi omwe adapatsidwawo amalembedwa motsatana.
Apa ndapeza kufotokozera komveka bwino (kwa ine ndekha):
3. Adjacency Vector ndi Associative Adjacency Array
Zinapezeka kuti wolemba mizere iyi, osakhala katswiri wamapulogalamu, koma yemwe nthawi ndi nthawi amachita ndi ma graph, nthawi zambiri amakhala ndi mndandanda wa m'mphepete. Zowonadi, ndizosavuta ngati graph ili ndi malupu angapo ndi m'mphepete. Ndipo kotero, popanga mindandanda yapamwamba ya m'mphepete, ndikupangira kuti ndisamalire "chitukuko / nthambi / kusintha / kusintha" kwawo, ndiko: vekitala yoyandikana ndi gulu loyandikana nalo.
3.1 Vector yoyandikana
Mlandu (a1): graph yopanda kulemera
Tiyitana vekitala yoyandikana ya graph yopanda kulemera kwa seti yoyitanidwa ya manambala onse (a[2i], a[2i+1],..., pomwe ndimawerengedwa c 0), momwe nambala iliyonse. a[2i], a[2i+1] imatchula m'mphepete mwa graph pakati pa vertices a[2i] ndi [2i+1], motsatana.
Mawonekedwe ojambulirawa alibe chidziwitso chokhudza ngati graph ikuwongoleredwa (zosankha zonse ndi zotheka). Mukamagwiritsa ntchito mawonekedwe a digraph, m'mphepete mwake mumawona kuti akuwongoleredwa kuchokera ku[2i] kupita ku[2i+1]. Apa ndi m'munsimu: kwa ma graph osalunjika, ngati kuli kofunikira, zofunikira za dongosolo la vertices zojambulira zitha kugwiritsidwa ntchito (mwachitsanzo, kuti vertex yokhala ndi mtengo wotsika wa nambala yomwe wapatsidwa imabwera poyamba).
Mu C ++, ndikofunikira kutchula vesi loyandikana nalo pogwiritsa ntchito std::vector, chifukwa chake dzina lachidziwitsochi.
Mlandu (a2): graph yopanda kulemera, zolemera za m'mphepete ndizokwanira
Pofananiza ndi chiwombankhanga (a1), timatcha vekitala yoyandikira ya graph yolemedwa yokhala ndi masikelo ophatikizika m'mphepete mwake kukhala seti yotsatiridwa (yozungulira) ya manambala (a[3i], a[3i+1], a[3i+2], ..., pamene ndimawerengeredwa c 0), pamene “katatu” kalikonse ka manambala a[3i], a[3i+1], a[3i+2] amatchula m’mphepete mwa graph pakati pa vertices yolembedwa a[3i] ndi[3i+1], motsatana, ndipo mtengo a [3i+2] ndi kulemera kwa m'mphepete. Grafu yotereyi imathanso kuwongolera kapena ayi.
Mlandu (b): graph yopanda kulemera, zolemera zopanda malire
Popeza ndizosatheka kusunga zinthu zosasinthika mu gulu limodzi (vector), mwachitsanzo, kutsatira zotsatirazi ndizotheka. Chithunzicho chimasungidwa muzotengera ziwiri, momwe vekitala yoyamba ndi vekitala yoyandikana ndi graph popanda kufotokoza zolemera, ndipo vekitala yachiwiri imakhala ndi zolemera zofananira (zotheka kukhazikitsa C++: std::pair ). Chifukwa chake, pamphepete yomwe imatanthauzidwa ndi ma vertices pansi pa indexes 2i, 2i + 1 ya vector yoyamba, kulemera kwake kudzakhala kofanana ndi chinthu chomwe chili pansi pa index I ya vector yachiwiri.
Chabwino, chifukwa chiyani izi zili zofunika?
Chabwino, wolemba mizere iyi adawona kuti ndizothandiza kuthetsa mavuto angapo. Chabwino, kuchokera pamalingaliro okhazikika, padzakhala zabwino zotsatirazi:
- Vector yoyandikana nayo, monganso zina zilizonse "zowerengera", ndizophatikizika, sizimakumbukira pang'ono kuposa matrix oyandikana nawo (pa ma graph ochepa), ndipo ndi yosavuta kugwiritsa ntchito.
- Ma vertices a graph, makamaka, amathanso kulembedwa ndi manambala olakwika. Bwanji ngati “kupotoza” koteroko kuli kofunika?
- Zithunzi zimatha kukhala ndi m'mphepete zingapo ndi malupu angapo, okhala ndi zolemera zosiyanasiyana (zabwino, zoyipa, ngakhale ziro). Palibe zoletsa pano.
- Mutha kugawanso zinthu zosiyanasiyana m'mphepete - koma kuti mudziwe zambiri, onani gawo 4.
Komabe, ziyenera kuvomerezedwa kuti "mndandanda" uwu sukutanthauza kuti mutha kufika m'mphepete mwachangu. Ndipo apa Associative Adjacency Array amabwera kudzapulumutsa, zomwe zikukambidwa pansipa.
3.2 Gulu loyandikana nalo
Choncho, ngati kupeza m'mphepete mwapadera, kulemera kwake ndi zinthu zina ndizofunikira kwa ife, ndipo zofunikira za kukumbukira sizimalola kugwiritsa ntchito matrix oyandikana nawo, ndiye tiyeni tiganizire momwe tingasinthire vekitala yoyandikana nayo kuti tithetse vutoli. Chifukwa chake, fungulo ndi m'mphepete mwa graph, yomwe imatha kufotokozedwa ngati manambala olamulidwa. Kodi izi zikuwoneka bwanji? Kodi sichofunikira mumagulu ophatikizana? Ndipo, ngati ndi choncho, n’chifukwa chiyani sitikuigwiritsa ntchito? Tikhale ndi gulu lophatikizana pomwe kiyi iliyonse - nambala yolumikizidwa - idzalumikizidwa ndi mtengo - nambala yeniyeni kapena nambala yeniyeni yomwe imafotokoza kulemera kwa m'mphepete. Mu C++, ndikofunikira kugwiritsa ntchito dongosololi potengera std::chidebe cha mapu (std::map , int> kapena std::map , double>), kapena std::multimap ngati mbali zingapo zikuyembekezeredwa. Chabwino, tili ndi dongosolo losungira ma graph omwe amatenga kukumbukira pang'ono kuposa mapangidwe a "matrix", amatha kufotokozera ma graph okhala ndi malupu angapo ndi m'mphepete, ndipo alibe ngakhale zofunikira zokhazikika pakusasinthika kwa manambala a vertex (sindikudziwa. amene amafunikira izi, komabe).
4. Zolemba za data ndizodzaza, koma pali china chake chikusowa
Ndipo ndizowona: pothetsa mavuto angapo, tingafunike kuyika zina m'mphepete mwa graph ndikuzisunga. Ngati ndi kotheka kuchepetsa izi mosadziwika bwino, ndiye kuti ndizotheka kusunga "ma graph okhala ndi zina zowonjezera" pogwiritsa ntchito mitundu yowonjezereka ya ma adjacency vector ndi associative adjacency array.
Kotero, tiyeni tikhale ndi graph yopanda kulemera, pamphepete iliyonse yomwe imayenera kusungidwa, mwachitsanzo, 2 zina zowonjezera zomwe zafotokozedwa ndi chiwerengero. Pachifukwa ichi, ndizotheka kufotokozera vector yake yoyandikana ngati njira yolamulidwa osati "awiri", koma "quartets" ya chiwerengero (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , pomwe a[2i+2] ndi[2i+3] zidzatsimikizira mawonekedwe a m'mphepete mwake. Kwa graph yokhala ndi miyeso yambiri ya m'mphepete, dongosololi nthawi zambiri limakhala lofanana (kusiyana kokha kudzakhala kuti zizindikirozo zidzatsatira kulemera kwa m'mphepete mwake ndipo zidzafotokozedwa ndi zinthu a[2i+3] ndi [2i+4] , ndipo m'mphepete mwake mudzafotokozedwa osati 4, koma manambala 5 olamulidwa). Ndipo kwa graph yokhala ndi zolemetsa zopanda malire, mawonekedwewo amatha kulembedwa mu gawo lake lopanda kulemera.
Mukamagwiritsa ntchito gulu lophatikizana la ma graph okhala ndi zolemera zochulukirapo, ndizotheka kufotokozera ngati mtengo osati nambala imodzi, koma gulu (vector) la manambala omwe amafotokozera, kuwonjezera pa kulemera kwa m'mphepete, zina zonse zofunika. Mawonekedwe. Panthawi imodzimodziyo, kusokonezeka kwa zolemetsa zosawerengeka kudzakhala kufunikira kutchula chizindikiro chokhala ndi nambala yoyandama (inde, izi ndizosokoneza, koma ngati palibe zizindikiro zambiri zoterozo, ndipo ngati simutero. Osawaika kukhala “onyenga” pawiri, pamenepo pasakhale kanthu) . Izi zikutanthawuza kuti mu C++ zowonjezera zowonjezera zowonjezera zitha kufotokozedwa motere: std::map , std::vector> kapena std::map , std :: vector, momwe mtengo woyamba mu "key-value-vector" udzakhala kulemera kwa m'mphepete, ndiyeno chiwerengero cha zizindikiro zake chilipo.
Zolemba:
Za ma graph ndi ma algorithms ambiri:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Ma algorithms: zomangamanga ndi kusanthula, kope lachiwiri: Trans. kuchokera ku Chingerezi - M.: Williams Publishing House, 2.
2. Harari Frank. Malingaliro azithunzi. M.: Mir, 1973.
Lipoti la wolemba za ma vector omwewo komanso magulu ophatikizika a adjacencies:
3. Chernoukhov S.A. Njira zoyimilira ndi kusunga ma graph / SA Chernouhov. Vector yoyandikana ndi mapu oyandikana nawo ngati ma data oyimira ma graph // Kutoleredwa kwa zolemba za International Science Science and Practical Conference "Mavuto pakukhazikitsa zotsatira zazinthu zatsopano ndi njira zowathetsera" (Saratov, Seputembara 14.09.2019, 2019). - Sterlitamak: AMI, 65, p. 69-XNUMX
Zothandiza pa intaneti pamutuwu:
4.
5.
Source: www.habr.com