Sema kila mtu
Katika dokezo hili, niliamua kuorodhesha miundo kuu ya data inayotumiwa kuhifadhi grafu katika sayansi ya kompyuta, na pia nitazungumza juu ya miundo michache zaidi ambayo kwa namna fulani "iliniangaza" kwangu.
Kwa hiyo, hebu tuanze. Lakini sio tangu mwanzo - nadhani sote tayari tunajua grafu ni nini na ni nini (iliyoelekezwa, isiyoelekezwa, yenye uzani, isiyo na uzito, na au bila kingo nyingi na vitanzi).
Kwa hiyo, twende. Je, tuna chaguo gani za miundo ya data ya "hifadhi ya grafu"?
1. Miundo ya data ya Matrix
1.1 Matrix ya ukaribu. Matrix ya kukaribiana ni matriki ambapo vichwa vya safu mlalo na safu vinalingana na nambari za vipeo vya grafu, na thamani ya kila kipengele chake a(i,j) huamuliwa na kuwepo au kutokuwepo kwa kingo kati ya vipeo. i na j (ni wazi kuwa kwa grafu isiyoelekezwa matrix kama hiyo itakuwa ya ulinganifu, au tunaweza kukubaliana kwamba tunahifadhi maadili yote juu ya diagonal kuu). Kwa grafu zisizo na uzito, a(i,j) inaweza kuwekwa na idadi ya kingo kutoka i hadi j (ikiwa hakuna makali kama hayo, basi a(i,j)= 0), na kwa grafu zilizopimwa, pia kwa uzani. (jumla ya uzito) ya kingo zilizotajwa.
1.2 Matrix ya matukio. Katika kesi hii, grafu yetu pia imehifadhiwa kwenye jedwali ambalo, kama sheria, nambari za safu zinalingana na nambari za wima zake, na nambari za safu zinalingana na kingo zilizohesabiwa hapo awali. Ikiwa vertex na makali ni tukio kwa kila mmoja, basi thamani isiyo ya sifuri imeandikwa kwenye seli inayolingana (kwa grafu zisizoelekezwa, 1 imeandikwa ikiwa vertex na makali ni tukio, kwa grafu zilizoelekezwa - "1" ikiwa makali. "hutoka" kutoka kwenye vertex na "-1" ikiwa "inajumuisha" ndani yake (ni rahisi kutosha kukumbuka, kwa sababu ishara ya "minus" inaonekana pia "imejumuishwa" katika namba "-1")). Kwa grafu zilizo na uzito, tena, badala ya 1 na -1, unaweza kutaja uzito wa jumla wa makali.
2. Miundo ya data ya hesabu
2.1 Orodha ya karibu. Naam, kila kitu kinaonekana kuwa rahisi hapa. Kila kipeo cha grafu kinaweza, kwa ujumla, kuhusishwa na muundo wowote wa kuhesabia (orodha, vekta, safu, ...), ambayo itahifadhi nambari za vipeo vyote karibu na ile iliyotolewa. Kwa grafu zilizoelekezwa, tutaongeza kwenye orodha kama hizo tu wima ambazo kuna ukingo wa "kuelekezwa" kutoka kwa kipeo cha kipengele. Kwa grafu zilizo na uzito utekelezaji utakuwa mgumu zaidi.
2.2 Orodha ya mbavu. Muundo maarufu wa data. Orodha ya kingo, kama Kapteni Obviousness anatuambia, kwa kweli ni orodha ya kingo za grafu, ambayo kila moja imeainishwa na kipeo cha kuanzia, kipeo cha mwisho (kwa grafu ambazo hazijaelekezwa mpangilio sio muhimu hapa, ingawa kwa kuunganishwa unaweza. tumia sheria mbalimbali, kwa mfano, kubainisha wima ili kuongeza) na uzito (kwa grafu zenye uzito pekee).
Unaweza kuangalia orodha za matrix zilizoorodheshwa hapo juu kwa undani zaidi (na kwa vielelezo), kwa mfano, .
2.3 Safu ya karibu. Sio muundo wa kawaida zaidi. Katika msingi wake, ni aina ya "kufunga" orodha za karibu katika muundo mmoja wa kuhesabu (safu, vector). Vitu vya kwanza vya n (kulingana na idadi ya vipeo vya grafu) vya safu kama hiyo vina fahirisi za kuanzia za safu sawa, kuanzia ambayo wima zote zilizo karibu na ile iliyopewa zimeandikwa kwa safu.
Hapa nilipata maelezo yanayoeleweka zaidi (kwangu):
3. Adjacency Vector na Associative Adjacency Array
Ilibadilika kuwa mwandishi wa mistari hii, sio kuwa mtaalamu wa programu, lakini ambaye mara kwa mara alishughulika na grafu, mara nyingi alishughulika na orodha za kingo. Hakika, ni rahisi ikiwa grafu ina loops nyingi na kingo. Na kwa hivyo, katika ukuzaji wa orodha za kawaida za kingo, napendekeza kuzingatia "maendeleo / tawi / urekebishaji / mabadiliko", ambayo ni: vekta ya karibu na safu ya ukaribu ya ushirika.
3.1 Vekta ya ukaribu
Kesi (a1): grafu isiyo na uzito
Tutaita vekta ya mkabala ya grafu isiyo na uzito seti iliyopangwa ya nambari sawia ya nambari kamili (a[2i], a[2i+1],..., ambapo nina nambari c 0), ambapo kila jozi ya nambari ni [2i], a[2i+1 ] inabainisha ukingo wa grafu kati ya vipeo a[2i] na [2i+1], mtawalia.
Umbizo hili la kurekodi halina taarifa kuhusu iwapo grafu inaelekezwa (chaguo zote mbili zinawezekana). Wakati wa kutumia umbizo la digrafu, kingo huzingatiwa kuelekezwa kutoka a[2i] hadi a[2i+1]. Hapa na chini: kwa grafu zisizoelekezwa, ikiwa ni lazima, mahitaji ya utaratibu wa wima za kurekodi yanaweza kutumika (kwa mfano, kwamba vertex yenye thamani ya chini ya nambari iliyopewa inakuja kwanza).
Katika C++, inashauriwa kutaja vekta ya karibu kwa kutumia std::vector, kwa hiyo jina la muundo huu wa data.
Kesi (a2): grafu isiyo na uzito, uzani wa ukingo ni kamili
Kwa mlinganisho na kipochi (a1), tunaita vekta ya mkabala ya grafu iliyopimwa yenye uzani kamili kuwa seti iliyopangwa (safu inayobadilika) ya nambari (a[3i], a[3i+1], a[3i+2], ..., ambapo nina nambari c 0), ambapo kila "pembetatu" ya nambari a[3i], a[3i+1], a[3i+2] inabainisha ukingo wa grafu kati ya vipeo vilivyo na nambari a[3i] na a[3i+1], mtawalia, na thamani a [3i+2] ni uzito wa makali haya. Grafu kama hiyo inaweza pia kuelekezwa au la.
Kesi (b): grafu isiyo na uzito, uzito wa ukingo usio kamili
Kwa kuwa haiwezekani kuhifadhi vipengele tofauti katika safu moja (vector), kwa mfano, utekelezaji unaofuata unawezekana. Grafu huhifadhiwa katika jozi ya vivekta, ambapo vekta ya kwanza ni vekta ya kukaribiana ya grafu bila kubainisha uzani, na vekta ya pili ina uzani unaolingana (utekelezaji unaowezekana wa C++: std::pair ) Kwa hivyo, kwa makali yaliyoelezwa na jozi ya wima chini ya indexes 2i, 2i + 1 ya vector ya kwanza, uzito utakuwa sawa na kipengele chini ya index i ya vector ya pili.
Naam, kwa nini hii ni muhimu?
Kweli, mwandishi wa mistari hii aliona ni muhimu sana kwa kutatua shida kadhaa. Kweli, kutoka kwa maoni rasmi, kutakuwa na faida zifuatazo:
- Vekta ya mkabala, kama muundo mwingine wowote wa "hesabu", ni thabiti kabisa, inachukua kumbukumbu kidogo kuliko matrix ya karibu (kwa grafu chache), na ni rahisi kutekeleza.
- Vipeo vya grafu, kimsingi, vinaweza pia kuwekwa alama na nambari hasi. Je, ikiwa "upotovu" kama huo unahitajika?
- Grafu zinaweza kuwa na kingo nyingi na vitanzi vingi, na uzani tofauti (chanya, hasi, hata sifuri). Hakuna vikwazo hapa.
- Unaweza pia kugawa mali tofauti kwa kingo - lakini kwa zaidi juu ya hilo, angalia sehemu ya 4.
Hata hivyo, ni lazima kukiri kwamba "orodha" hii haimaanishi upatikanaji wa haraka kwa makali. Na hapa Safu ya Uunganisho wa Associative inakuja kuwaokoa, ambayo inajadiliwa hapa chini.
3.2 Safu ya kukaribiana ya ushirika
Kwa hiyo, ikiwa upatikanaji wa makali maalum, uzito wake na mali nyingine ni muhimu kwetu, na mahitaji ya kumbukumbu hayaturuhusu kutumia matrix ya karibu, basi hebu fikiria jinsi tunaweza kubadilisha vector ya karibu ili kutatua tatizo hili. Kwa hivyo, ufunguo ni ukingo wa grafu, ambayo inaweza kubainishwa kama jozi ya nambari kamili zilizoagizwa. Je, hii inaonekanaje? Je! sio ufunguo katika safu ya ushirika? Na, ikiwa ni hivyo, kwa nini hatutekelezi? Hebu tuwe na safu shirikishi ambapo kila ufunguo - jozi kamili ya nambari zilizopangwa - zitahusishwa na thamani - nambari kamili au nambari halisi inayobainisha uzito wa ukingo. Katika C++, inashauriwa kutekeleza muundo huu kulingana na std::chombo cha ramani (std::map , int> au std::map , double>), au std::multimap ikiwa kingo nyingi zinatarajiwa. Kweli, tuna muundo wa kuhifadhi grafu ambayo inachukua kumbukumbu kidogo kuliko muundo wa "matrix", inaweza kufafanua grafu zilizo na vitanzi na kingo nyingi, na haina hata mahitaji madhubuti ya kutokuwa hasi kwa nambari za vertex (sijui. nani anahitaji hii, lakini bado).
4. Miundo ya data imejaa, lakini kuna kitu kinakosekana
Na ni kweli: wakati wa kutatua shida kadhaa, tunaweza kuhitaji kugawa sifa fulani kwenye kingo za grafu na, ipasavyo, kuzihifadhi. Iwapo inawezekana kupunguza vipengele hivi kwa nambari kamili, basi inawezekana kuhifadhi "grafu zilizo na vipengele vya ziada" kwa kutumia matoleo yaliyopanuliwa ya vekta ya karibu na safu ya adjacency ya ushirika.
Kwa hiyo, hebu tuwe na grafu isiyo na uzito, kwa kila makali ambayo ni muhimu kuhifadhi, kwa mfano, vipengele 2 vya ziada vilivyotajwa na integers. Katika kesi hii, inawezekana kufafanua vekta yake inayopakana kama seti iliyoamriwa sio ya "jozi", lakini ya "robota" za nambari kamili (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , ambapo a[2i+2] na[2i+3] zitabainisha sifa za ukingo unaolingana. Kwa grafu iliyo na uzani kamili wa kingo, mpangilio kwa ujumla unafanana (tofauti pekee itakuwa kwamba sifa zitafuata uzito wa ukingo na zitabainishwa na vipengele a[2i+3] na a[2i+4] , na makali yenyewe yataelezwa sio 4, lakini nambari 5 zilizoagizwa). Na kwa grafu yenye uzani usio kamili, vipengele vinaweza kuandikwa kwenye sehemu yake isiyo na uzito.
Wakati wa kutumia safu shirikishi ya kukaribiana kwa grafu zilizo na uzani kamili wa makali, inawezekana kubainisha kama thamani sio nambari moja, lakini safu (vekta) ya nambari zinazobainisha, pamoja na uzito wa ukingo, zingine zote muhimu. vipengele. Wakati huo huo, usumbufu kwa kesi ya uzani usio kamili itakuwa hitaji la kutaja ishara iliyo na nambari ya kuelea (ndio, hii ni usumbufu, lakini ikiwa hakuna ishara nyingi kama hizo, na ikiwa hautafanya. Usiziweke kuwa "janja" maradufu, basi inaweza kuwa si kitu) . Hii ina maana kwamba katika C++ safu zilizopanuliwa za ukaribu za ushirika zinaweza kufafanuliwa kama ifuatavyo: std::map , std::vector> au std::map , std::vector, ambayo thamani ya kwanza katika "muhimu-thamani-vector" itakuwa uzito wa makali, na kisha majina ya nambari ya sifa zake ziko.
Fasihi:
Kuhusu grafu na algoriti kwa ujumla:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithms: ujenzi na uchambuzi, toleo la 2: Trans. kutoka kwa Kiingereza - M.: Williams Publishing House, 2011.
2. Harari Frank. Nadharia ya grafu. M.: Mir, 1973.
Ripoti ya mwandishi kuhusu vekta hizi na safu shirikishi za viambatanisho:
3. Chernoukhov S.A. Vekta ya ukaribu na safu shirikishi ya kukaribiana kama njia za kuwakilisha na kuhifadhi grafu / SA Chernouhov. Vekta ya ukaribu na ramani ya karibu kama miundo ya data kuwakilisha grafu // Mkusanyiko wa makala ya Mkutano wa Kimataifa wa Sayansi na Vitendo "Matatizo ya kutekeleza matokeo ya maendeleo ya ubunifu na njia za kuyatatua" (Saratov, Septemba 14.09.2019, 2019). - Sterlitamak: AMI, 65, p. 69-XNUMX
Vyanzo muhimu vya mtandaoni kwenye mada:
4.
5.
Chanzo: mapenzi.com