Qof walba raalli.
Qoraalkan, waxaan go'aansaday in aan liis gareeyo qaababka xogta ugu muhiimsan ee loo isticmaalo in lagu kaydiyo garaafyada sayniska kombiyuutarka, sidoo kale waxaan ka hadli doonaa dhowr dhismo oo kale oo sidan ah oo si uun "crystallized" ii ah.
Markaa, aan bilowno. Laakin maaha bilawgii hore - Waxaan filayaa in aynu dhamaanteen naqaanay waxa garaafku yahay iyo waxa ay yihiin (lagu hagayo, aan la jihayn, miisaan lahayn, aan miisaan lahayn, leh ama aan lahayn geeso badan iyo siddo).
Markaa, aan tagno. Ikhtiyaarkee ah qaababka xogta ee "kaydinta garaafka" ayaan haysanaa?
1. Qaabdhismeedka xogta Matrix
1.1 Matrix adjacency. Matrixka ku dheggan waa matrix halka ciwaanka safka iyo tiirka ay u dhigmaan tirooyinka geesaha garaafka, iyo qiimaha mid kasta oo ka mid ah curiyayaasha a(i,j) waxaa lagu go'aamiyaa joogitaanka ama maqnaanshaha geesaha u dhexeeya geesaha. i iyo j ( way caddahay in garaaf aan toos ahayn shaxdu waxay noqon doontaa mid siman, ama waxaan ku heshiin karnaa inaan ku kaydinno dhammaan qiyamka kaliya ee ka sarreeya xariiqda weyn). Garaafyada aan miisaanka lahayn, a(i,j) waxaa lagu dejin karaa tirada cidhifyada min i ilaa j (haddii aanay jirin cidhifkaas, ka dib a(i,j)= 0), iyo garaafyada miisaanka leh, sidoo kale miisaanka (miisaanka guud) ee cidhifyada la sheegay.
1.2 Matrix dhacdo. Xaaladdan oo kale, garaafkeena ayaa sidoo kale lagu kaydiyaa miis kaas oo, sida caadiga ah, tirooyinka safka ah waxay u dhigmaan tirooyinka cidhifyada, iyo tirooyinka tiirarka waxay u dhigmaan cidhifyada horay loo tiriyey. Haddii cidhif iyo cidhif isku dhacaan, markaa qiimo aan eber ahayn ayaa lagu qoraa unugga u dhigma (garaafyada aan toosnayn, 1 waxa la qorayaa haddii cidhifku iyo cidhifku dhacdo, garaafyo jihaysan - "1" haddii cidhifka "ka baxa" ka soo baxa cirifka iyo "-1" haddii "ay ku jirto" ku jira (waa sahlan tahay in la xasuusto, sababtoo ah calaamadda "laga jaray" waxay sidoo kale u muuqataa inay "ku jirto" lambarka "-1")). Garaafyada miisaanka leh, mar labaad, halkii 1 iyo -1, waxaad qeexi kartaa wadarta miisaanka cidhifka.
2. Qaabdhismeedka xogta tirinta
2.1 Liiska ku xiga. Waa hagaag, wax walba waxay u muuqdaan kuwo fudud halkan. Dabool kasta oo garaafku, guud ahaan, wuxuu la xidhiidhi karaa qaab-dhismeedka tirinta (liiska, vector, array, ...), kaas oo kaydin doona tirooyinka dhammaan darafyada ku xiga kan la bixiyay. Garaafyada toosan, waxaan ku dari doonaa liiskan oo kaliya darafyada ay ku jirto cidhifka "la toosan" ee ka soo jeeda muuqaal. Garaafyada miisaanka leh fulintu waxay noqon doontaa mid aad u adag.
2.2 Liiska feeraha. Qaab dhismeedka xogta caanka ah Liiska cidhifyada, sida uu Captain Caddayn inoo sheegay, dhab ahaantii waa liis cidhifyada garaafka, mid kasta oo ka mid ah waxaa lagu qeexaa cidhifyada garaafyada, cidhifyada dhamaadka (garaafyada aan toosnayn amarku maaha mid muhiim ah halkan, inkastoo mideynta aad awoodid. adeegso xeerar kala duwan, tusaale ahaan, qeexida darafyada si ay u kordhaan) iyo miisaanka (garaafyada miisaanka leh oo keliya).
Waxaad si faahfaahsan u eegi kartaa liisaska jaantusyada kor ku taxan (iyo sawiro), tusaale ahaan, .
2.3 Isku xidhid. Ma aha qaabka ugu caansan. Xagga xudunta u ah, waa nooc ka mid ah liisaska ku dheggan ee "baakaynta" ee hal qaab-dhismeedka tirinta (array, vector). Qaybta hore ee n (sida ku cad tirada geesaha garaafku) ee cutubyada noocan oo kale ah waxay ka kooban yihiin tusmooyin bilow ah oo isku mid ah, kuwaas oo ka bilaabmaya dhammaan cidhifyada ku dheggan kan la bixiyay oo isku xigta.
Halkan waxaan ka helay sharraxaadda ugu badan ee la fahmi karo (naftayda):
3. Adjacency Vector and Associative Adjacency Array
Waxaa soo baxday in qoraaga khadadkan, uusan ahayn barnaamij-yaqaan xirfadle ah, balse si xilliyo ah wax uga qaban jiray garaafyada, inta badan uu wax ka qaban jiray liisaska geesaha. Runtii, way ku habboon tahay haddii garaafku leeyahay siddo iyo geeso badan. Sidaas darteed, horumarinta liisaska caadiga ah ee cidhifyada, waxaan soo jeedinayaa in fiiro gaar ah loo yeesho "horumarkooda/ laantooda/wax ka beddelka/isbeddelka", kuwaas oo ah: vector-ka ag-dhawaanshaha iyo isku-xidhka isku-xidhka.
3.1 Adjacency vector
Case (a1): garaaf aan miisaan lahayn
Waxa aanu ugu yeedhi doonaa garaaf aan miisaan lahayn oo la amray oo ah tiro isku mid ah waa a[2i], a[2i+1] waxay qeexaysaa cidhifka garaafka u dhexeeya barafka a[0i] iyo a[2i+2], siday u kala horreeyaan.
Qaabka duubista kuma jiraan macluumaad ku saabsan in garaafku hagayo iyo in kale (labada doorasho waa suurtagal). Markaad isticmaalayso qaabka garaafka, cidhifka waxaa loo arkaa in laga hagayo a[2i] ilaa a[2i+1]. Halkan iyo hoosta: garaafyada aan toosnayn, haddii loo baahdo, shuruudaha nidaamka duubista ayaa lagu dabaqi karaa (tusaale, in cirifka qiimaha hoose ee lambarka loo qoondeeyey uu yimaado marka hore).
Gudaha C ++, waxaa lagu talinayaa in lagu qeexo vector ku xiga adoo isticmaalaya std :: vector, markaa magaca qaabka xogtan.
Case (a2): garaafka aan miisaanka lahayn, miisaanka cidhifku waa wada jir
Marka loo eego kiis (a1), waxaanu ugu yeedhnaa vector-ka ag-dhawaanshaha garaaf miisaan leh oo leh miisaanyo cidhif ah oo la amray (array) nambaro ah (a[3i], a[3i+1], a[3i+2], . iyo a[0i+3], siday u kala horreeyaan, iyo qiimaha a [3i+1] waa miisaanka cidhifkan. Jaantuska noocan oo kale ah sidoo kale waa la tilmaami karaa ama ma aha.
Case (b): garaafka aan miisaanka lahayn, miisaanka cidhifyada aan isugeyn
Maadaama aysan suurtagal ahayn in lagu kaydiyo walxaha kala duwan ee hal array (vector), tusaale ahaan, hirgelinta soo socota waa suurtogal. Garaafku waxa uu ku kaydsan yahay laba qaybood oo kala duwan, kuwaas oo vector-ka koowaad uu yahay garaafka agtiisa iyada oo aan la cayimin miisaanka, qaybta labaadna waxa ay ka kooban tahay miisaannada u dhigma (fulinta suurtagalka ah ee C ++: std :: lammaane ). Haddaba, cidhif ay ku qeexan yihiin laba-geesood oo hoos imanaya tusmooyinka 2i, 2i+1 ee vector-ka koowaad, miisaanku waxa uu la mid noqonayaa curiyaha hoos yimaada index i of vector labaad.
Hagaag, maxay tani lama huraan u tahay?
Hagaag, qoraaga xariiqyadan ayaa u arkay inay faa'iido weyn u leedahay xallinta tiro dhibaatooyin ah. Waa hagaag, marka laga eego aragtida rasmiga ah, waxaa jiri doona faa'iidooyinka soo socda:
- Xuubka ku dheggan, sida qaab-dhismeedka "tira-koobka" ee kale, aad buu u kooban yahay, wuxuu qaataa xusuusta ka yar marka loo eego shaxanka ku dheggan (garaafyada yar yar), waana sahlan tahay in la hirgeliyo.
- Cidhifyada garaafka, mabda 'ahaan, sidoo kale waxaa lagu calaamadin karaa tirooyinka taban. Maxaa dhacaya haddii loo baahdo "qallooc" noocaas ah?
- Garaafyadu waxay ka koobnaan karaan geeso badan iyo siddo badan, oo leh miisaanyo kala duwan (positive, negative, xitaa eber). Ma jiraan wax xannibaad ah halkan.
- Waxa kale oo aad ku meelayn kartaa guryo kala duwan cidhifyada - laakiin wax badan oo taas ku saabsan, eeg qaybta 4.
Si kastaba ha ahaatee, waa in la qiraa in "liiskan" aanu ka turjumayn gelitaanka degdega ah ee cidhifka. Oo halkan waxaa soo samatabbixinaya Associative Adjacency Array, kaas oo hoos looga hadlay.
3.2 Isku xidhka isku xidhka
Sidaa darteed, haddii helitaanka cidhif gaar ah, miisaankiisa iyo sifooyinka kale ayaa muhiim noo ah, shuruudaha xusuustana ma ogola inaan isticmaalno matrixka ku dheggan, ka dibna aan ka fikirno sida aan u bedeli karno vector-ka ag-dhow si loo xalliyo dhibaatadan. Haddaba, furuhu waa cidhifka garaafka, kaas oo lagu tilmaami karo integers la dalbaday. Maxay tani u egtahay? Miyaanay fure ku ahayn isku xidhka associative? Oo, hadday sidaas tahay, maxaynu u fulin waynay? Aynu yeelano array associative ah halkaas oo fure kasta --labo la dalbay oo isugeyn ah - lagu xiriirin doono qiime - tiro ama tiro dhab ah oo qeexaysa miisaanka cidhifka. Gudaha C++, waxaa lagu talinayaa in la hirgeliyo qaab-dhismeedkan ku salaysan std :: weelka khariidad (std :: khariidad) , int> ama std :: khariidad , double>), ama std :: multimap haddii geeso badan la filayo. Hagaag, waxaanu leenahay qaab-dhismeed lagu kaydiyo garaafyada qaada xusuusta ka yar marka loo eego qaab-dhismeedka “matrix”, waxay qeexi karaan garaafyada leh siddo iyo geeso badan, oo aan xitaa lahayn shuruudo adag oo loogu talagalay kuwa aan xumaanta lahayn ee tirooyinka vertex (ma aqaano). yaa u baahan tan, laakiin weli).
4. Qaab dhismeedka xogta waa buuxaan, laakiin wax baa maqan
Waana run: marka la xalinayo tiro dhibaatooyin ah, waxaa laga yaabaa inaan u baahanno inaan ku meeleyno qaar ka mid ah sifooyinka garaafyada iyo, si waafaqsan, kaydin. Haddii ay suurtogal tahay in si aan mugdi lahayn loo yareeyo sifooyinkaas si isku mid ah, markaa waxaa suurtogal ah in la kaydiyo "garaafyada leh sifooyin dheeraad ah" iyada oo la adeegsanayo noocyada la dheereeyey ee vector-ka ag-dhowrka iyo associative adjacency array.
Sidaa darteed, aynu haysano garaaf aan miisaan lahayn, gees kasta oo ay lagama maarmaan tahay in lagu kaydiyo, tusaale ahaan, 2 sifooyin dheeraad ah oo lagu qeexay isugeynta. Xaaladdan oo kale, waxa suurtagal ah in lagu qeexo vector-keeda u dhow sida go'an la amray oo aan ahayn "lammaanaha", laakiin ee "quartets" ee isugeynta (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , halka a[2i+2] iyo a[2i+3] ay go'aamin doonaan sifooyinka cidhifka u dhigma. Jaantuska leh miisaanka isku dhafka cidhifyada, nidaamku guud ahaan wuu la mid yahay (farqiga kaliya ayaa noqon doona in sifooyinku raaci doonaan miisaanka cidhifka waxaana lagu qeexi doonaa curiyeyaasha a[2i+3] iyo a[2i+4] , iyo cidhifka laftiisa ayaa lagu qeexi doonaa ma aha 4, laakiin 5 tirooyinka la dalbaday). Iyo garaaf leh miisaan cidhif ah oo aan isugeyn, astaamaha waxaa lagu qori karaa qaybtiisa aan miisaan lahayn.
Marka la isticmaalayo isku xidhka isku xidhka garaafyada leh miisaanyada cidhifyada, waxa suurtogal ah in lagu qeexo qiime ahaan ma aha tiro keliya, laakiin array (vector) ee nambarada tilmaamaya, marka lagu daro miisaanka cidhifka, dhammaan lagama maarmaanka u ah Astaamaha. Isla mar ahaantaana, dhib la'aanta kiiska miisaanka aan dhexdhexaadka ahayn waxay noqon doontaa baahida loo qabo in lagu qeexo calaamad leh nambar sabeynaya (haa, tani waa dhib, laakiin haddii aysan jirin calaamado badan oo noocaas ah, iyo haddii aad sameyso Ha u dhigin kuwo aad u "khiyaamo" laba jibaaran, ka dibna waxba ma noqon karaan) . Tani waxay ka dhigan tahay in C++ isku xidhka isku xidhka la fidiyay lagu qeexi karo sida soo socota: std:: khariidad , std :: vector> ama std :: khariidad , std :: vector, kaas oo qiimaha ugu horreeya ee "key-value-vector" uu noqon doono miisaanka cidhifka, ka dibna nambarada tirooyinka ee sifooyinkeeda ayaa ku yaal.
Suugaanta:
Ku saabsan garaafyada iyo algorithms guud ahaan:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithms: dhismaha iyo falanqaynta, daabacaadda 2aad: Trans. ka Ingiriis – M.: Williams Publishing House, 2011.
2. Harari Frank. Aragtida garaafka. M.: Mir, 1973.
Warbixinta qoraaga ee ku saabsan isla falgalkan iyo isku xidhka isku xidhka
3. Chernoukhov S.A. Isku-xirnaanta isku-xirnaanta iyo isku-xirnaanta isku-xirnaanta sida habab lagu matalo loona kaydiyo garaafyada / SA Chernouhov. Khariidadda ku dhegganaanshaha iyo khariidadda u dhow sida qaab-dhismeedka xogta si ay u matalaan garaafka // Ururinta maqaallada Shirka Caalamiga ah ee Sayniska iyo Dhaqanka "Dhibaatooyinka hirgelinta natiijooyinka horumarinta hal-abuurka leh iyo siyaabaha loo xalliyo" (Saratov, Sebtembar 14.09.2019, 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Ilaha internetka ee waxtarka leh ee mawduuca:
4.
5.
Source: www.habr.com