Molweni nonke.
Kweli nqaku, ndigqibe ekubeni ndidwelise ezona ziseko zedatha zisetyenziselwa ukugcina iigrafu kwisayensi yekhompyuter, kwaye ndiza kuthetha malunga nesibini esinezakhiwo ezithe ngandlel 'ithile "ziyikristale" kum.
Ngoko, masiqale. Kodwa hayi kwasekuqaleni-ndicinga ukuba sonke sele sisazi ukuba yintoni igrafu kwaye yintoni na (iqondiswe, ingajoliswanga, ilinganiswe, ingenasisindo, kunye okanye ngaphandle kwemiphetho emininzi kunye neelophu).
Ngoko, masihambe. Zeziphi iinketho zezakhiwo zedatha "zokugcinwa kwegrafu" esinazo?
1. Izakhiwo zedatha yeMatrix
1.1 Imatrix ekufutshane. I-adjacency matrix yimatrix apho umqolo kunye nezihloko zekholamu zihambelana namanani ee-vertices zegrafu, kunye nexabiso lezinto zayo nganye a(i,j) imiselwa bubukho okanye ukungabikho kwemiphetho phakathi kwee-vertices. i kunye no-j (kucacile ukuba kwigrafu engaqondiswanga i-matrix enjalo iya kuba yi-symmetrical, okanye sinokuvuma ukuba sigcina onke amaxabiso ngaphezulu kwe-diagonal engundoqo). Kwiigrafu ezingenabunzima, u-a(i,j) unokumiselwa ngenani lesiphelo ukusuka ku-i ukuya ku-j (ukuba akukho siphelo sinjalo, ngoko a(i,j)= 0), kunye neegrafu ezinobunzima, nangobunzima. (ubunzima bubonke) bemida ekhankanyiweyo.
1.2 Iziganeko zematrix. Kule meko, igrafu yethu iphinde igcinwe kwitheyibhile apho, njengomthetho, amanani omqolo ahambelana namanani ee-vertices zayo, kwaye iinombolo zekholomu zihambelana nemida yangaphambili. Ukuba i-vertex kunye nomphetho zisehlo omnye komnye, ngoko ixabiso elingeyo-zero libhalwa kwiseli ehambelanayo (kwiigrafu ezingabhalwanga, i-1 ibhaliwe ukuba i-vertex kunye ne-edge zisehlo, kwiigrafu eziqhelanisiweyo - "1" ukuba umda "iphuma" kwi-vertex kunye ne "-1" ukuba "ibandakanya" kuyo (kulula ukuyikhumbula, kuba uphawu "lokukhupha" lubonakala "lubandakanyiwe" kwinani elithi "-1")). Kwiigrafu ezinobunzima, kwakhona, endaweni ye-1 kunye ne -1, ungacacisa ubunzima obupheleleyo bomphetho.
2. Uluhlu lwedatha yobalo
2.1 Uluhlu olusondeleyo. Ewe, yonke into ibonakala ilula apha. I-vertex nganye yegrafu inakho, ngokubanzi, ukunxulunyaniswa nalo naluphi na ulwakhiwo lobalo (uluhlu, i-vector, uluhlu, ...), oluya kugcina amanani azo zonke ii-vertices ezikufuphi nale inikiweyo. Kwiigrafu eziqondisiweyo, siya kongeza kuluhlu olunjalo kuphela ezo nkqo kukho isiphelo "esiqondisiweyo" esivela kwi-vertex yesici. Kwiigrafu ezinobunzima ukuphunyezwa kuya kuba nzima ngakumbi.
2.2 Uluhlu lweembambo. Ulwakhiwo lwedatha oludumileyo. Uluhlu lwemiphetho, njengoko uKapteni Obviousness esixelela, eneneni luluhlu lweencam zegrafu, nganye kuzo ichazwe yi-vertex yokuqala, i-vertex yokuphela (kwiigrafu ezingabhalwanga umyalelo awubalulekanga apha, nangona ukudibanisa sebenzisa imigaqo eyahlukeneyo, umzekelo, ukucacisa ii-vertices ukuze zinyuke) kunye nobunzima (kwigrafu ezinobunzima kuphela).
Ungajonga kuluhlu lwematrix oludweliswe ngasentla ngokweenkcukacha ngakumbi (kunye nemifanekiso), umzekelo, .
2.3 Uluhlu olusondeleyo. Ayisisona sakhiwo siqhelekileyo. Kwisiseko sayo, luhlobo "lokupakisha" uluhlu olusondeleyo kwisakhiwo esinye sobalo (uluhlu, i-vector). Eyokuqala n (ngokwenani lee-vertices zegrafu) iziqalelo zoluhlu olunjalo ziqulathe izalathisi zokuqala zoluhlu olufanayo, ziqala apho zonke ii-vertices ezimelene nale inikiweyo zibhalwe kumqolo.
Apha ndifumene eyona ngcaciso iqondakalayo (kum):
3. IVector yokudibana kunye ne-Associative Adjacency Array
Kwavela ukuba umbhali wale migca, engenguye umdwelisi weprogram, kodwa oye wajongana rhoqo neegrafu, ngokuqhelekileyo wayejongana noluhlu lwamaphethelo. Ngokwenene, ilungile ukuba igrafu inezijikelezo ezininzi kunye nemiphetho. Kwaye ke, ekuphuhliseni izintlu zakudala zemiphetho, ndiphakamisa ukuba ndinikele ingqalelo "kuphuhliso / isebe / ukuguqulwa / ukuguqulwa", oku kukuthi: i-vector ekufutshane kunye ne-associative adjacency array.
3.1 Ivektha esecaleni
Ityala (a1): igrafu engenabunzima
Siza kubiza iVektha ekufutshane yegrafu engenabunzima njengeseti ecwangcisiweyo enani elilinganayo leenombolo ezipheleleyo (a[2i], a[2i+1],..., apho inombolo ibalwa ngo-c 0), apho ipere nganye yamanani yi[2i], a[2i+1 ] ikhankanya ungqameko lwegrafu phakathi kwee-vertices a[2i] kunye no-a[2i+1], ngokulandelelanayo.
Le fomati yokurekhoda ayinalo ulwazi malunga nokuba igrafu iqondiswe (zombini iinketho zinokwenzeka). Xa usebenzisa ifomathi ye-digraph, i-edge ithathwa njengeqondiswe kwi-[2i] ukuya kwi-[2i +1]. Apha nangezantsi: kwiigrafu ezingabhalwanga, ukuba kuyimfuneko, iimfuno zomyalelo wokurekhoda kwee-vertices zingasetyenziswa (umzekelo, ukuba i-vertex enexabiso eliphantsi lenani elinikezelweyo liza kuqala).
Kwi-C++, kuyacetyiswa ukuba ucacise i-vector ekufutshane usebenzisa i-std::vector, ngoko ke igama lesi sakhiwo sedatha.
Ityala (a2): igrafu engenabunzima, iintsimbi zomphetho ziphelele
Ngothelekiso ngendawo (a1), sibiza iVektha ekufutshane yegrafu enobunzima obupheleleyo iseti ecwangcisiweyo (uluhlu oluguqukayo) lwamanani (a[3i], a[3i+1], a[3i+2], ..., apho ndinenombolo engu-c 0), apho “i-triplet” nganye yamanani a[3i], a[3i+1], a[3i+2] ichaza udini lwegrafu phakathi kweendidi ezinenombolo a[3i] kunye ne[3i+1], ngokulandelelanayo, kwaye ixabiso i [3i+2] bubunzima bolu ngqameko. Igrafu enjalo inokukwalathisa okanye hayi.
Ityala (b): igrafu engenabunzima, ubunzima bomphetho obungaphelelanga
Ekubeni kungenakwenzeka ukugcina izinto ezingafaniyo kuluhlu olunye (i-vector), umzekelo, ukuphunyezwa okulandelayo kunokwenzeka. Igrafu igcinwe kwiperi yevektha, apho ivektha yokuqala yigrafu esecaleni kwevektha ngaphandle kokuchaza iintsimbi, kwaye ivektha yesibini iqulathe ubunzima obuhambelanayo (ukuphunyezwa okunokwenzeka kweC++: std::isibini ). Ngaloo ndlela, kwi-edge echazwe ngababini bee-vertices phantsi kwee-indexes 2i, i-2i + 1 ye-vector yokuqala, ubunzima buya kufana ne-element phantsi kwe-index i ye-vector yesibini.
Ewe, kutheni oku kuyimfuneko?
Ewe, umbhali wale migca uyifumene iluncedo kakhulu ekusombululeni inani leengxaki. Ewe, ngokwembono esemthethweni, kuya kubakho oku kulandelayo:
- Ivektha esecaleni, njengaso nasiphi na esinye isakhiwo “sokubala”, ixinene kakhulu, ithatha inkumbulo encinci kuneyematrix esecaleni (yeegrafu ezinqabileyo), kwaye kulula ukuyiphumeza.
- Ii-vertices zegrafu, ngokomgaqo, zinokuphawulwa ngamanani a-negative. Kuthekani ukuba “ukugqwethwa” okunjalo kuyafuneka?
- Iigrafu zinokuqulatha imiphetho emininzi kunye neelophu ezininzi, ezinobunzima obahlukeneyo (ezilungileyo, ezimbi, nokuba zero). Akukho zithintelo apha.
- Unokwabela iipropathi ezahlukeneyo kwimida - kodwa ngakumbi malunga naloo nto, bona icandelo lesi-4.
Nangona kunjalo, kufuneka kuvunywe ukuba olu "luhlu" aluthethi ukufikelela ngokukhawuleza kumda. Kwaye apha i-Associative Adjacency Array iza kuhlangula, ekuxoxwa ngayo ngezantsi.
3.2 Uluhlu oludibanisayo oludibanisayo
Ngoko ke, ukuba ukufikelela kumda othile, ubunzima bayo kunye nezinye iimpawu zibalulekile kuthi, kwaye iimfuno zememori azisivumeli ukuba sisebenzise i-matrix esondeleyo, ngoko makhe sicinge malunga nendlela esinokuyitshintsha ngayo i-vector ekufutshane ukusombulula le ngxaki. Ngoko ke, isitshixo sisiphelo segrafu, esinokuchazwa njengenani elipheleleyo eliodolweyo. Ijongeka njani le nto? Ngaba ayingositshixo kuluhlu oludibeneyo? Kwaye, ukuba kunjalo, kutheni singayiphumezi? Masibe noluhlu oludibanisayo apho isitshixo ngasinye - ipere edityanisiweyo yee-integers - siyakunxulunyaniswa nexabiso - inani elipheleleyo okanye inani lokwenyani elichaza ubunzima bomphetho. Kwi-C++, kuyacetyiswa ukuba uphumeze olu lwakhiwo lusekwe kwi-std::isikhongozeli seemephu (std::map , int> okanye std::maphu , double>), okanye std::multimap ukuba imiphetho emininzi ilindelekile. Kulungile, sinesakhiwo sokugcina iigrafu ezithatha imemori encinci kune "matrix" izakhiwo, ezinokuchaza iigrafu ezinamaqhina amaninzi kunye nemiphetho, kwaye ayinayo kwaneemfuno ezingqongqo zokungakhethi-negativity kwamanani e-vertex (andazi). ngubani ofuna oku, kodwa kunjalo).
4. Ulwakhiwo lwedatha lugcwele, kodwa kukho into engekhoyo
Kwaye kuyinyani: xa uxazulula inani leengxaki, sinokudinga ukunika iimpawu ezithile kwimida yegrafu kwaye, ngokufanelekileyo, sizigcine. Ukuba kuyenzeka ukunciphisa ngokungaguqukiyo ezi mpawu zibe zii-integers, ngoko ke kuyenzeka ukugcina “iigrafu ezineempawu ezongezelelweyo” usebenzisa iinguqulelo ezandisiweyo zevektha esecaleni kunye ne-associative adjacency array.
Ngoko ke, masibe negrafu engenabunzima, kumda ngamnye apho kuyimfuneko ukugcina, umzekelo, iimpawu ezi-2 ezongezelelweyo ezichazwe ngamanani apheleleyo. Kule meko, kunokwenzeka ukucacisa i-vector ekufutshane nayo njengeseti eyalelweyo kungekhona "yezibini", kodwa "ye-quartet" yee-integers (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , apho u[2i+2] kunye no[2i+3] ziya kugqiba iimpawu zomphetho ohambelana nawo. Kwigrafu eneentsimbi ezipheleleyo zemiphetho, ulungelelwaniso lufana ngokubanzi (umahluko kuphela uya kuba kukuba iimpawu ziya kulandela ubunzima bomphetho kwaye ziya kucaciswa ziziqalelo a[2i+3] kunye ne[2i+4] , kunye nomphetho ngokwawo uya kuchazwa kungekhona i-4, kodwa iinombolo ezi-5 ezicwangcisiweyo). Kwaye igrafu enezisindo ze-non-integer edge, iimpawu zingabhalwa kwinxalenye yayo engenasisindo.
Xa usebenzisa i-associative adjacency array kwiigrafu ezinobunzima bomphetho opheleleyo, kuyenzeka ukukhankanya njengexabiso hayi inani elinye, kodwa uluhlu (vector) lwamanani oluchazayo, ukongeza kubunzima bomphetho, zonke ezinye eziyimfuneko. Iimbonakalo. Kwangaxeshanye, ukuphazamiseka kwimeko yobunzima obungaphelelanga kuya kuba yimfuneko yokuchaza uphawu olunenombolo edadayo (ewe, oku kukuphazamiseka, kodwa ukuba akukho miqondiso emininzi kangaka, kwaye ukuba awufuni. Ungazimiseli zibe “zikhohlisayo” ngokuphindwe kabini, ngoko zisenokungabi nto) . Oku kuthetha ukuba kwi-C++ eyandisiweyo yoluhlu oludityanisiweyo lunokuchazwa ngolu hlobo lulandelayo: std::map , std::vector> okanye std::map , std :: i-vector, apho ixabiso lokuqala "kwi-key-value-vector" liya kuba nobunzima bomda, kwaye ke ukutyunjwa kwamanani eempawu zayo kufumaneka.
Uncwadi:
Malunga neegrafu kunye ne-algorithms ngokubanzi:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Ii-algorithms: ukwakhiwa kunye nohlalutyo, i-2nd edition: Trans. ukusuka kwisiNgesi – M.: Williams Publishing House, 2011.
2. UHarari Frank. Ithiyori yegrafu. UM.: Mir, ngo-1973.
Ingxelo yombhali malunga nale vector efanayo kunye noluhlu oludibeneyo lweendawo ezikufutshane:
3. Chernoukhov S.A. Ivektha ye-adjacency kunye ne-associative adjacency array njengeendlela zokumela kunye nokugcina iigrafu / i-SA Chernouhov. I-vector ye-adjacency kunye nemephu ekufutshane njengezakhiwo zedatha ukumela igrafu // Ukuqokelelwa kwamanqaku eNkomfa yeNzululwazi kunye neNkomfa yeZizwe ngeZizwe "Iingxaki zokuphumeza iziphumo zophuhliso olutsha kunye neendlela zokuzisombulula" (Saratov, Septemba 14.09.2019, 2019). -Sterlitamak: AMI, 65, iphe. 69-XNUMX
Imithombo eluncedo kwi-intanethi ngesihloko:
4.
5.
umthombo: www.habr.com