Sanibonani nonke.
Kule nothi, nginqume ukuklelisa izakhiwo zedatha eziyinhloko ezisetshenziselwa ukugcina amagrafu kwisayensi yekhompiyutha, futhi ngizophinde ngikhulume ngezinye ezimbalwa izakhiwo ezinjalo ngandlela thize "ezicwebezelayo" kimi.
Ngakho, ake siqale. Kodwa hhayi kusukela ekuqaleni - ngicabanga ukuthi sonke sesiyazi kakade ukuthi igrafu iyini nokuthi iyini (iqondiswe, ingaqondiwe, inesisindo, ingenasisindo, noma ingenayo imiphetho eminingi namalophu).
Ngakho, asihambe. Yiziphi izinketho zezakhiwo zedatha "zokugcinwa kwegrafu" esinazo?
1. Izakhiwo zedatha ye-Matrix
1.1 I-matrix eseduze. I-adjacency matrix iyi-matrix lapho umugqa nezihloko zekholomu zihambisana nezinombolo zamathrethi egrafu, futhi inani le-elementi ngayinye yalo a(i,j) linqunywa ukuba khona noma ukungabikho konqenqema phakathi kwama-vertices. i no-j (kuyacaca ukuthi kugrafu engaqondile leyo matrix izoba yi-symmetrical, noma singavuma ukuthi sigcina wonke amanani ngaphezu kwediagonal eyinhloko kuphela). Kumagrafu angenasisindo, u-a(i,j) angasethwa ngenani lamaphethelo ukusuka ku-i kuye ku-j (uma lungekho unqenqema olunjalo, khona-ke u-a(i,j)= 0), kanye namagrafu anesisindo, futhi ngesisindo. (isisindo esiphelele) semiphetho eshiwo.
1.2 I-matrix yesigameko. Kulokhu, igrafu yethu iphinde igcinwe etafuleni lapho, njengomthetho, izinombolo zomugqa zihambisana nezinombolo zama-vertices ayo, futhi izinombolo zekholomu zihambisana nemiphetho yezinombolo zangaphambili. Uma i-vertex kanye nonqenqema kuyisigameko komunye nomunye, kusho ukuthi inani elingelona uziro libhalwa kuseli elihambisanayo (kumagrafu angaqondile, kubhalwa u-1 uma i-vertex kanye nonqenqema kuyisigameko, kumagrafu aqondisiwe - "1" uma unqenqema. "iphuma" isuka ku-vertex kanye no-"-1" uma "ihlanganisa" kuyo (kulula ukuyikhumbula, ngoba uphawu "lokususa" lubonakala sengathi "lufakiwe" enombolweni "-1")). Kumagrafu anesisindo, futhi, esikhundleni sika-1 no -1, ungacacisa isisindo esiphelele sonqenqema.
2. Izakhiwo zedatha yokubala
2.1 Uhlu oluseduze. Hhayi-ke, yonke into ibonakala ilula lapha. I-vertex ngayinye yegrafu, ngokuvamile, ingahlotshaniswa nanoma yisiphi isakhiwo sokubala (uhlu, i-vector, amalungu afanayo, ...), azogcina izinombolo zawo wonke ama-vertices eduze kwaleyo enikeziwe. Kumagrafu aqondisiwe, sizokwengeza ohlwini olunjalo kuphela lawo mathwithi okunomkhawulo "oqondisiwe" ovela ku-vertex yesici. Kumagrafu anesisindo ukuqaliswa kuzoba nzima kakhulu.
2.2 Uhlu lwezimbambo. Isakhiwo sedatha esidumile. Uhlu lwamaphethelo, njengoba uCaptain Obviousness esitshela, empeleni luwuhlu lwamaphethelo egrafu, ngalinye elicaciswe i-vertex yokuqala, i-vertex yokugcina (kumagrafu angaqondile umyalelo awubalulekile lapha, nakuba ngokuhlanganisa ungakwazi. sebenzisa imithetho eyahlukene, isibonelo, ukucacisa ama-vertices ukuze akhule) kanye nesisindo (kumagrafu anesisindo kuphela).
Ungabheka uhlu lwe-matrix olufakwe ngenhla ngemininingwane eyengeziwe (kanye nemifanekiso), isibonelo, .
2.3 I-Adjacency array. Akusona isakhiwo esivame kakhulu. Emgogodleni wayo, iwuhlobo “lokupakisha” izinhlu eziseduze zibe isakhiwo esisodwa sokubala (uhlu, i-vector). Eyokuqala n (ngokwenani lama-vertices egrafu) izakhi zamalungu afanayo anjalo aqukethe izinkomba zokuqala zamalungu afanayo afanayo, aqala lapho wonke ama-vertices ancikene naleyo enikeziwe abhalwe umugqa.
Lapha ngithole incazelo eqondakala kakhulu (mina ngokwami):
3. I-Adjacency Vector kanye ne-Associative Adjacency Array
Kwavela ukuthi umbhali wale migqa, engeyena umhleli wezinhlelo, kodwa osebenza ngezikhathi ezithile ngamagrafu, ngokuvamile wayebhekana nezinhlu zemiphetho. Ngempela, kulula uma igrafu inamalophu amaningi namaphethelo. Ngakho-ke, ekuthuthukisweni kohlu lwakudala lwamaphethelo, ngiphakamisa ukuthi nginake “ukuthuthukiswa/igatsha/ukuguqulwa/ukuguqulwa”, okungukuthi: i-adjacency vector kanye ne-associative adjacency array.
3.1 I-vector eseduze
Ikesi (a1): igrafu engenasisindo
Sizobiza i-adjacency vector yegrafu engenasisindo ngesethi e-odiwe enani elilinganayo lama-integers (a[2i], a[2i+1],..., lapho ngibhalwe khona izinombolo c 0), lapho ipheya ngayinye yezinombolo ithi a[2i], a[2i+1 ] icacisa umphetho wegrafu phakathi kwama-vertices a[2i] kanye no-a[2i+1], ngokulandelanayo.
Le fomethi yokurekhoda ayinalo ulwazi mayelana nokuthi igrafu iqondiswe yini (zombili izinketho zingenzeka). Uma usebenzisa ifomethi ye-digraph, unqenqema lubhekwa njengoluqondiswe kusuka ku[2i] kuya ku[2i+1]. Lapha nangezansi: kumagrafu angaqondile, uma kunesidingo, izimfuneko zokuhleleka kwama-vertices aqoshiwe zingasetshenziswa (isibonelo, ukuthi i-vertex enenani eliphansi lenombolo eyabelwe yona iza kuqala).
Ku-C++, kuyatuseka ukuthi ucacise i-adjacency vector usebenzisa i-std::vector, yingakho igama lalesi sakhiwo sedatha.
Ikesi (a2): igrafu engenasisindo, izisindo zomphetho ziyinombolo ephelele
Ngokufanisa nekesi (a1), sibiza ivekhtha eseduze yegrafu enesisindo esiphelele sonqenqema ngesethi ehleliwe (amalungu afanayo ashintshashintshayo) yezinombolo (a[3i], a[3i+1], a[3i+2], ..., lapho nginezinombolo khona ngo-c 0), lapho “unxantathu” ngamunye wezinombolo a[3i], a[3i+1], a[3i+2] icacisa unqenqema lwegrafu phakathi kwamagama anombolo a[3i] kanye no-a[3i+1], ngokulandelanayo, futhi inani elingu- [3i+2] liyisisindo salo mkhawulo. Igrafu enjalo ingabuye iqondiswe noma cha.
Ikesi (b): igrafu engenasisindo, izisindo zomphetho ezingaphelele
Njengoba kungenakwenzeka ukugcina izakhi ezihlukahlukene ohlwini olulodwa (i-vector), isibonelo, ukuqaliswa okulandelayo kungenzeka. Igrafu igcinwa kupheya lamavekhtha, lapho ivekhtha yokuqala iyivekhtha eseduze yegrafu ngaphandle kokucacisa izisindo, futhi ivekhtha yesibili iqukethe izisindo ezihambisanayo (ukuqaliswa okungenzeka ku-C++: std::pair ). Ngakho-ke, onqenqemeni oluchazwe ipheya yamanani ngaphansi kwezinkomba 2i, 2i+1 wevekhtha yokuqala, isisindo sizolingana nesici esingaphansi kwenkomba i yevekhtha yesibili.
Nokho, kungani lokhu kudingekile?
Nokho, umbhali wale migqa ukuthole kuwusizo kakhulu ukuxazulula izinkinga eziningi. Yebo, ngokombono osemthethweni, kuzoba nezinzuzo ezilandelayo:
- I-adjacency vector, njenganoma yisiphi esinye isakhiwo “esibalayo”, iminyene impela, ithatha inkumbulo encane kune-adjacency matrix (kumagrafu agqagqene), futhi kulula ukuyisebenzisa.
- Ama-vertices egrafu, ngokomthetho, angaphawulwa futhi ngezinombolo ezinegethivu. Kuthiwani uma “ukuphendukezelwa” okunjalo kudingekile?
- Amagrafu angaqukatha imiphetho eminingi namaluphu amaningi, anesisindo esihlukile (esihle, esinegethivu, ngisho uziro). Ayikho imikhawulo lapha.
- Ungakwazi futhi ukwabela izakhiwo ezihlukene emaphethelweni - kodwa ukuze uthole okwengeziwe ngalokho, bheka isigaba 4.
Nokho, kufanele kuvunywe ukuthi lolu “hlu” alusho ukufinyelela ngokushesha onqenqemeni. Futhi lapha i-Associative Adjacency Array iza ukusiza, okuxoxwe ngayo ngezansi.
3.2 I-Associative adjacency array
Ngakho-ke, uma ukufinyelela onqenqemeni oluthile, isisindo salo nezinye izakhiwo kubalulekile kithi, futhi izidingo zenkumbulo azisivumeli ukuba sisebenzise i-matrix eseduze, ake sicabange ukuthi singayishintsha kanjani i-vector eseduze ukuze sixazulule le nkinga. Ngakho-ke, ukhiye uwunqenqema lwegrafu, olungacaciswa njengenani eliphelele eli-odiwe. Kubukeka kanjani lokhu? Akusona yini isihluthulelo kuhlu lokuhlanganisa? Futhi, uma kunjalo, kungani singakusebenzisi? Masibe ne-associative array lapho ukhiye ngamunye - ipheya enamba e-odiwe - izohlotshaniswa nenani - inombolo ephelele noma inombolo yangempela ecacisa isisindo sonqenqema. Ku-C++, kuyatuseka ukuthi usebenzise lesi sakhiwo ngokusekelwe ku-std::isitsha semephu (std::map , int> noma std::map , double>), noma std::multimap uma kulindelwe imiphetho eminingi. Hhayi-ke, sinesakhiwo sokugcina amagrafu esithatha inkumbulo encane kunezakhiwo "ze-matrix", engachaza amagrafu anamaluphu amaningi nemiphetho, futhi ayinazo ngisho nezidingo eziqinile zokungabi negativity kwezinombolo ze-vertex (angazi ubani okudingayo lokhu, kodwa namanje).
4. Izakhiwo zedatha zigcwele, kodwa kukhona okushodayo
Futhi kuyiqiniso: lapho sixazulula izinkinga eziningi, kungase kudingeke sinikeze izici ezithile emaphethelweni egrafu futhi, ngokufanele, sizigcine. Uma kungenzeka ukwehlisa ngokusobala lezi zici zibe izinombolo eziphelele, khona-ke kungenzeka ukugcina "amagrafu anezici ezengeziwe" kusetshenziswa izinguqulo ezinwetshiwe ze-adjacency vector kanye ne-associative adjacency array.
Ngakho-ke, masibe negrafu engenasisindo, onqenqemeni ngalunye okudingeka ukuligcina, isibonelo, izici ezi-2 ezengeziwe ezicaciswe izinombolo. Kulokhu, kungenzeka ukuchaza i-vector yayo eseduze njengesethi e-odayo hhayi “yamapheya”, kodwa “kwamaquartets” ezinombolo eziphelele (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , lapho okuthi a[2i+2] kanye no-a[2i+3] kuzonquma izici zonqenqema oluhambisanayo. Kugrafu enezisindo eziphelele zamaphethelo, ukuhleleka ngokuvamile kuyefana (umehluko kuphela uzoba ukuthi izibaluli zizolandela isisindo sonqenqema futhi zizocaciswa izici a[2i+3] kanye no-a[2i+4] , futhi unqenqema ngokwalo luzocaciswa hhayi 4, kodwa izinombolo ezi-5 ezi-odwe). Futhi ngegrafu enezisindo zonqenqema ezingaphelele, izici zingabhalwa engxenyeni yayo engenasisindo.
Uma usebenzisa i-associative adjacency array yamagrafu anezisindo zonqenqema eziphelele, kungenzeka ukucacisa njengenani hhayi inombolo eyodwa, kodwa amalungu afanayo (ivektha) yezinombolo ezicacisayo, ngaphezu kwesisindo sonqenqema, konke okunye okudingekayo. izici. Ngasikhathi sinye, ukuphazamiseka kwecala lezisindo ezingezona eziphelele kuzoba isidingo sokucacisa isibonakaliso ngenombolo yephuzu elintantayo (yebo, lokhu kuwukuphazamiseka, kepha uma zingekho izimpawu ezinjalo eziningi, futhi uma ungawabeke kabili “akhohlisayo”, angabe esaba lutho) . Lokhu kusho ukuthi ku-C++ ama-adjacency ahlanganisiwe anwetshiwe angachazwa kanje: std::map , std::vector> noma std::map , std::vector, lapho inani lokuqala "kukhiye-value-vector" lizoba isisindo sonqenqema, bese kuba nezinombolo zezimpawu zayo.
Imibhalo
Mayelana namagrafu nama-algorithms ngokuvamile:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Ama-algorithms: ukwakhiwa nokuhlaziya, uhlelo lwesi-2: Trans. kusukela esiNgisini - M.: Williams Publishing House, 2011.
2. Harari Frank. Ithiyori yegrafu. M.: Mir, 1973.
Umbiko wombhali mayelana nalawa ma-vector afanayo kanye ne-associative array of adjacencies:
3. Chernoukhov S.A. I-Adjacency Vector kanye ne-associative adjacency array njengezindlela zokumela nokugcina amagrafu / SA Chernouhov. I-Adjacency Vector kanye nemephu eseduze njengezakhiwo zedatha ezizomela igrafu // Ukuqoqwa kwama-athikili eNkomfa Yamazwe Ngamazwe Yesayensi Nokusebenza “Izinkinga zokusebenzisa imiphumela yentuthuko emisha nezindlela zokuzixazulula” (Saratov, Septhemba 14.09.2019, 2019). - I-Sterlitamak: AMI, 65, p. 69-XNUMX
Imithombo ewusizo eku-inthanethi ngesihloko:
4.
5.
Source: www.habr.com