Sannu kowa da kowa.
A cikin wannan bayanin, na yanke shawarar jera manyan tsarin bayanan da ake amfani da su don adana hotuna a cikin ilimin kwamfuta, kuma zan kuma yi magana game da wasu ma'aurata da irin wannan tsarin da ko ta yaya suka “crystallized” a gare ni.
Don haka, bari mu fara. Amma ba daga farkon ba - Ina tsammanin duk mun riga mun san menene jadawali da abin da suke (directed, undirected, weighted, unweighted, with ko ba tare da mahara gefuna da madaukai).
Don haka, mu tafi. Wadanne zaɓuɓɓuka don tsarin bayanai don “ajiye jadawali” muke da shi?
1. Matrix data Tsarin
1.1 Adjacency matrix. Matrix adjacency matrix ne inda layin layi da kanun shafi suka yi daidai da lambobi na madaidaitan jadawali, kuma darajar kowanne daga cikin abubuwansa a(i,j) an ƙaddara ta gaban ko rashin gefuna tsakanin madaidaitan. i da j (a bayyane yake cewa ga jadawali wanda ba a ba da izini ba irin wannan matrix zai kasance mai ma'ana, ko kuma za mu iya yarda cewa muna adana duk dabi'u kawai sama da babban diagonal). Don jadawalai marasa nauyi, a(i,j) za a iya saita ta da adadin gefuna daga i zuwa j (idan babu irin wannan gefen, sannan a(i,j) = 0), da kuma hotuna masu nauyi, kuma ta nauyi. (jimlar nauyi) na gefuna da aka ambata.
1.2 Matrix aukuwa. A wannan yanayin, jadawalinmu kuma ana adana shi a cikin tebur wanda, a matsayin mai mulkin, lambobin jere sun dace da lambobi na madaidaitan sa, kuma lambobin ginshiƙan sun dace da gefuna da aka riga aka ƙidaya. Idan juzu'i da gefen sun faru da juna, ana rubuta ƙimar da ba sifili ba a cikin tantanin halitta daidai (don jadawali, an rubuta 1 idan tsayin da gefen ya faru, don zane-zane masu daidaitawa - "1" idan gefen. "fita" daga juzu'i da "-1" idan "ya haɗa da" a ciki (yana da sauƙin tunawa, saboda alamar "raguwa" kuma alama tana "haɗe" a cikin lambar "-1")). Don ma'auni masu nauyi, sake, maimakon 1 da -1, za ku iya ƙayyade jimlar nauyin gefen.
2. Tsarin bayanan ƙididdiga
2.1 Lissafin madaidaici. To, komai yana da sauƙi a nan. Kowane juzu'in jadawali na iya, gaba ɗaya, ana haɗa shi da kowane tsarin ƙidayar (jeri, vector, array, ...), wanda zai adana lambobi na duk madaidaicin da ke kusa da wanda aka bayar. Don zane-zanen da aka ba da umarni, za mu ƙara zuwa irin wannan jeri kawai waɗancan madaidaitan waɗanda ke da gefen “directed” daga gefen siffa. Don jadawalai masu nauyi aiwatarwa zai fi rikitarwa.
2.2 Jerin haƙarƙari. Shahararren tsarin bayanai. Jerin gefuna, kamar yadda Kyaftin Bayyanar ya gaya mana, ainihin jerin gefuna ne na jadawali, kowannensu an ƙayyade shi ta wurin farawa, ƙarshen ƙarshen (don jadawali ba tare da izini ba tsari ba shi da mahimmanci a nan, kodayake don haɗin kai za ku iya. Yi amfani da ƙa'idodi daban-daban, misali, ƙididdige madaidaicin don haɓakawa) da nauyi (don hotuna masu nauyi kawai).
Kuna iya duba lissafin matrix da aka jera a sama da ƙarin daki-daki (kuma tare da misalai), misali, .
2.3 Tsare-tsare na adjacency. Ba tsarin da ya fi kowa ba. A ainihin sa, nau'i ne na jerin abubuwan da ke kusa da "packing" a cikin tsarin ƙidaya ɗaya (array, vector). Na farko n (bisa ga adadin madaidaitan jadawali) abubuwan da ke cikin irin wannan jeri sun ƙunshi fihirisar farawa na tsararrun iri ɗaya, waɗanda suke farawa daga inda aka rubuta duk wasu maƙallan da ke kusa da wanda aka bayar a jere.
Anan na sami bayani mafi fahimta (ga kaina):
3. Adjacency Vector and Associative Adjacency Array
Ya bayyana cewa marubucin waɗannan layin, ba kasancewar ƙwararren mai tsara shirye-shirye ba ne, amma wanda lokaci-lokaci yana mu'amala da jadawali, galibi yana yin ma'amala da jerin gefuna. Lalle ne, ya dace idan jadawali yana da madaukai da gefuna masu yawa. Sabili da haka, a cikin ci gaban lissafin gefuna na al'ada, Ina ba da shawarar kula da su "haɓaka / reshe / gyare-gyare / maye gurbin", wato: vector da ke kusa da haɗin gwiwa.
3.1 Adjacency vector
Case (a1): jadawali mara nauyi
Za mu kira vector na kusa don jadawali mara nauyi wani tsari da aka ba da umarni na adadin madaidaicin lamba (a[2i], a[2i+1],..., inda aka ƙidaya ni c 0), wanda kowane lambobi biyu a ciki. shine a[2i], a[2i+1] yana ƙayyade gefen jadawali tsakanin madaidaitan a[2i] da [2i+1], bi da bi.
Wannan tsarin rikodi ba ya ƙunsar bayani game da ko jadawali ya kasance (duk zaɓukan biyu suna yiwuwa). Lokacin amfani da tsarin digraph, ana ɗaukar gefen a matsayin jagora daga a[2i] zuwa [2i+1]. Anan da ƙasa: don jadawalai marasa jagora, idan ya cancanta, ana iya amfani da buƙatun don oda na rikodi (misali, ƙarshen tare da ƙaramin ƙimar lambar da aka sanya masa ya fara zuwa).
A cikin C++, yana da kyau a saka madaidaicin vector ta amfani da std :: vector, saboda haka sunan wannan tsarin bayanan.
Case (a2): jadawali mara nauyi, ma'aunin nauyi lamba ne
Ta hanyar kwatankwacin hali (a1), muna kiran vector na kusa don hoto mai ma'auni tare da ma'aunin ma'aunin gefen lamba saiti (tsari mai ƙarfi) na lambobi (a[3i], a [3i+1], a [3i+2], ..., inda aka ƙidaya ni c 0), inda kowane "sau uku" na lambobi a[3i], a [3i+1], a [3i+2] ya ƙayyade gefen jadawali tsakanin madaidaicin ƙididdiga a[3i] da a[3i+1], bi da bi, kuma darajar a [3i+2] ita ce nauyin wannan gefen. Irin wannan jadawali kuma ana iya yin jagora ko a'a.
Case (b): jadawali mara nauyi, ma'aunin ma'aunin gefen marar lamba
Tun da yake ba shi yiwuwa a adana abubuwa daban-daban a cikin tsararru ɗaya (vector), alal misali, aiwatarwa mai zuwa yana yiwuwa. Ana adana jadawali a cikin nau'i-nau'i guda biyu, wanda vector na farko shine madaidaicin jadawali ba tare da ƙayyade ma'auni ba, kuma vector na biyu ya ƙunshi ma'aunin ma'auni daidai (yiwuwar aiwatarwa don C ++: std :: biyu). ). Don haka, don gefen da aka siffanta ta biyu na nisa a ƙarƙashin maƙasudi 2i, 2i+1 na vector na farko, nauyin zai kasance daidai da kashi a ƙarƙashin fihirisar i na vector na biyu.
To, me yasa wannan ya zama dole?
To, marubucin waɗannan layukan ya ga yana da amfani sosai don magance matsaloli da yawa. To, daga ra'ayi na yau da kullun, za a sami fa'idodi masu zuwa:
- Matsakaicin haɗin gwiwa, kamar kowane tsarin “ƙididdigewa”, yana da ƙanƙanta sosai, yana ɗaukar ƙarancin ƙwaƙwalwar ajiya fiye da matrix na kusa (don jadawali kaɗan), kuma yana da sauƙin aiwatarwa.
- Matsakaicin jadawali, bisa manufa, kuma ana iya yiwa alama da lambobi mara kyau. Idan ana buƙatar irin wannan “karkatar” fa?
- Hotuna na iya ƙunsar gefuna da yawa da madaukai masu yawa, tare da ma'auni daban-daban (tabbatacce, korau, ko da sifili). Babu ƙuntatawa a nan.
- Hakanan zaka iya sanya kadarori daban-daban zuwa gefuna - amma don ƙarin akan hakan, duba sashe na 4.
Duk da haka, dole ne a yarda cewa wannan "jeri" baya nufin saurin isa ga gefen. Kuma a nan Associative Adjacency Array ya zo don ceto, wanda aka tattauna a kasa.
3.2 Tsari na haɗin gwiwa
Don haka, idan samun dama ga takamaiman gefen, nauyinsa da sauran kaddarorin yana da mahimmanci a gare mu, kuma buƙatun ƙwaƙwalwar ajiya ba su ƙyale mu mu yi amfani da matrix adjacency ba, to, bari mu yi tunanin yadda za mu iya canza vector adjacency don magance wannan matsala. Don haka, maɓalli shine gefen jadawali, wanda za'a iya ƙididdige shi azaman nau'i-nau'i na lamba. Menene wannan kama? Shin ba maɓalli ba ne a cikin tsararrun haɗin gwiwa? Kuma, idan haka ne, me ya sa ba za mu aiwatar da shi ba? Bari mu sami tsararrun haɗin gwiwa inda kowane maɓalli - nau'i-nau'i na lamba da aka ba da oda - za a haɗa shi da ƙima - lamba ko ainihin lamba wanda ke ƙayyadad da nauyin gefen. A cikin C ++, yana da kyau a aiwatar da wannan tsari bisa ga std :: kwandon taswira (std :: taswira) , int> ko std :: taswira , biyu>), ko std :: multimap idan ana sa ran gefuna da yawa. Da kyau, muna da tsari don adana jadawalai waɗanda ke ɗaukar ƙarancin ƙwaƙwalwar ajiya fiye da tsarin “matrix”, suna iya ayyana jadawali tare da madaukai da gefuna da yawa, kuma ba shi da madaidaicin buƙatu don rashin ƙarancin lambobi (Ban sani ba). wanda yake buƙatar wannan, amma har yanzu).
4. Tsarin bayanai sun cika, amma wani abu ya ɓace
Kuma gaskiya ne: lokacin da za mu magance matsalolin da dama, muna iya buƙatar sanya wasu halaye zuwa gefuna na jadawali kuma, daidai da haka, adana su. Idan zai yiwu a rage waɗannan fasalulluka ba tare da wata shakka ba zuwa lamba, to, yana yiwuwa a adana irin waɗannan "zane-zane tare da ƙarin fasali" ta amfani da ƙarin nau'ikan vector na adjacency da haɗin kai.
Don haka, bari mu sami jadawali mara nauyi, ga kowane gefen abin da ya wajaba don adanawa, alal misali, ƙarin fasali 2 da aka ƙayyade ta lamba. A wannan yanayin, yana yiwuwa a ayyana vector na kusa da shi azaman saitin da aka ba da umarni ba na “biyu” ba, amma na “quartets” na lamba (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , inda a[2i+2] da [2i+3] za su tantance halayen gefen da ya dace. Don jadawali tare da ma'aunin ƙididdiga na gefuna, tsari gabaɗaya yayi kama da (bambancin kawai shine cewa halayen zasu bi nauyin gefen kuma abubuwan a[2i+3] da a[2i+4] za su bayyana su. , kuma gefen kanta za a ƙayyade ba 4 ba, amma lambobi 5 da aka ba da umarni). Kuma ga jadawali tare da ma'aunin ma'aunin gefen da ba na lamba ba, ana iya rubuta fasalin cikin sashin da ba shi da nauyi.
Lokacin amfani da tsarin haɗin haɗin gwiwa don jadawalai masu ma'aunin gefen lamba, yana yiwuwa a ƙididdige ƙima ba lamba ɗaya ba, amma tsararru (vector) na lambobi waɗanda ke ƙayyadad da, ban da nauyin gefen, duk sauran larura. fasali. A lokaci guda, rashin jin daɗi ga yanayin ma'aunin ma'aunin nauyi ba zai zama buƙatar saka alamar tare da lamba mai iyo (eh, wannan rashin jin daɗi ne, amma idan babu irin waɗannan alamun da yawa, kuma idan kun yi haka). 't saita su ma "m" sau biyu, to, yana iya zama ba kome ba) . Wannan yana nufin cewa a cikin C++ za'a iya bayyana ma'anar ma'anar haɗin gwiwa kamar haka: std :: taswira. , std :: vector > ko std :: taswira , std :: vector, wanda darajar farko a cikin "key-value-vector" za ta kasance nauyin gefen, sa'an nan kuma ana samun alamun lambobi na halayensa.
Littattafai:
Game da zane-zane da algorithms gabaɗaya:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithms: gini da bincike, 2nd edition: Trans. daga Turanci – M.: Williams Publishing House, 2011.
2. Harari Frank. Ka'idar zane. M.: Mir, 1973.
Rahoton marubucin game da waɗannan nau'ikan nau'ikan nau'ikan abubuwan haɗin gwiwa:
3. Chernoukhov S.A. Adjacency vector da associative adjacency array azaman hanyoyin wakilci da adana hotuna / SA Chernouhov. Adjacency vector da taswirar kusanci azaman tsarin bayanai don wakiltar jadawali // Tarin labarai na taron Kimiyya da Aiki na kasa da kasa "Matsalolin aiwatar da sakamakon sabbin ci gaba da hanyoyin magance su" (Saratov, Satumba 14.09.2019, 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Shafukan kan layi masu amfani kan batun:
4.
5.
source: www.habr.com