Halo a h-uile duine.
Anns an nota seo, chuir mi romham liosta a dhèanamh de na prìomh structaran dàta a thathas a’ cleachdadh airson grafaichean a stòradh ann an saidheans coimpiutaireachd, agus bruidhnidh mi cuideachd mu dhà no dhà eile de na structaran sin a bha “criostalach” ann an dòigh air choireigin dhomh.
Mar sin, tòisichidh sinn. Ach chan ann bhon fhìor thoiseach - tha mi a 'smaoineachadh gu bheil fios againn uile mu thràth dè a th' ann an graf agus dè a th 'annta (stiùirichte, neo-stiùiridh, cuideam, gun chuideam, le no às aonais ioma-iomall agus lùban).
Mar sin, rachamaid. Dè na roghainnean a th’ againn airson structaran dàta airson “stòradh grafa”?
1. Structaran dàta matrix
1.1 Matrix faisg air làimh. Is e matrix a th’ anns a’ mhaitrix faisg air far a bheil cinn nan sreath agus nan colbhan a’ freagairt ri àireamhan vertices a’ ghraf, agus tha luach gach aon de na h-eileamaidean aige a(i,j) air a dhearbhadh le làthaireachd no neo-làthaireachd oirean eadar vertices. i agus j (tha e soilleir gum bi matrix mar sin co-chothromach airson graf neo-stiùirichte, no faodaidh sinn aontachadh gum bi sinn a’ stòradh a h-uile luach a-mhàin os cionn a’ phrìomh thrannsa). Airson grafaichean gun chuideam, faodar a(i,j) a shuidheachadh leis an àireamh oirean bho i gu j (mura h-eil iomall mar sin ann, an uairsin a(i, j) = 0), agus airson grafaichean le cuideam, cuideachd leis a’ chuideam (cuideam iomlan) de na h-oirean ainmichte.
1.2 matrix tachartas. Anns a 'chùis seo, tha an graf againn cuideachd air a stòradh ann an clàr anns a bheil, mar riaghailt, na h-àireamhan sreath a' freagairt ri àireamhan a vertices, agus tha àireamhan nan colbhan a 'freagairt ri oirean ro-àireamhaichte. Ma tha vertex agus oir a’ tachairt ri chèile, tha luach neo-neoni air a sgrìobhadh anns a’ chill fhreagarrach (airson grafaichean neo-stiùirichte, tha 1 air a sgrìobhadh ma tha an vertex agus an oir a’ tachairt, airson grafaichean treòraichte - “1” ma tha an oir “fàgail” bhon vertex agus “-1” ma tha “a’ toirt a-steach” innte (tha e furasta gu leòr cuimhneachadh, oir tha coltas gu bheil an soidhne “minus” cuideachd “air a ghabhail a-steach” san àireamh “-1”). Airson grafaichean le cuideam, a-rithist, an àite 1 agus -1, faodaidh tu cuideam iomlan an oir a shònrachadh.
2. Structaran dàta àireamhachd
2.1 Liosta faisg air làimh. Uill, tha e coltach gu bheil a h-uile dad sìmplidh an seo. Faodaidh gach vertex den ghraf, san fharsaingeachd, a bhith co-cheangailte ri structar àireamhachd sam bith (liosta, vectar, sreath, ...), a chumas àireamhan nan vertices uile ri taobh an tè a chaidh a thoirt seachad. Airson grafaichean stiùirichte, cha chuir sinn ri liosta mar sin ach na h-earrainnean sin aig a bheil oir “stiùirichte” bho vertex feart. Airson grafaichean le cuideam bidh am buileachadh nas iom-fhillte.
2.2 Liosta de na ribs. Structar dàta mòr-chòrdte. Tha an liosta oirean, mar a tha Caiptean Obviousness ag innse dhuinn, gu dearbh na liosta de oirean a’ ghraf, gach aon dhiubh air a shònrachadh leis an vertex tòiseachaidh, an vertex crìochnachaidh (airson grafaichean neo-stiùiridh chan eil an òrdugh cudromach an seo, ged a dh’ fhaodadh tu airson aonachadh. diofar riaghailtean a chleachdadh, mar eisimpleir, a’ sònrachadh na vertices ann an òrdugh a’ meudachadh) agus cuideam (airson grafaichean le cuideam a-mhàin).
Faodaidh tu coimhead air na liostaichean matrix gu h-àrd ann am barrachd mionaideachd (agus le dealbhan), mar eisimpleir, .
2.3 Sreath faisg air làimh. Chan e an structar as cumanta. Aig a chridhe, tha e na sheòrsa de liostaichean ri taobh “pacadh” ann an aon structar àireamhachd (sreath, vectar). Anns a 'chiad n (a rèir an àireamh de dh' uinneanan a 'ghraf) tha na h-eileamaidean de leithid de raon a' toirt a-steach clàran tòiseachaidh an aon sreath, a 'tòiseachadh bhon a tha a h-uile vertice faisg air an fhear a chaidh a thoirt seachad air a sgrìobhadh ann an sreath.
An seo lorg mi am mìneachadh as so-thuigsinn (dhomh fhìn):
3. Vector Adjacency and Associative Adjacency Array
Thionndaidh e a-mach gun robh ùghdar nan loidhnichean sin, gun a bhith na phrògramadair proifeasanta, ach a bhiodh a ’dèiligeadh ri grafaichean bho àm gu àm, gu tric a’ dèiligeadh ri liostaichean oirean. Gu dearbh, tha e goireasach ma tha grunn lùban is oirean air a’ ghraf. Agus mar sin, ann a bhith a’ leasachadh nan liostaichean clasaigeach de dh’oirean, tha mi a’ moladh aire a thoirt don “leasachadh/meur/mion-atharrachadh/mutation”, is iad sin: an vectar faisg air làimh agus an t-sreath dlùth-cheangail.
3.1 Vector faisg air làimh
Cùis (a1): graf gun chuideam
Canaidh sinn vectar faisg air làimh airson graf gun chuideam seata òrdaichte de dh’àireamh chothromach de shlànuighear (a[2i], a[2i+1],..., far a bheil i air a h-àireamhachadh c 0), anns a bheil gach paidhir àireamhan is a[2i], tha a[2i+1] a' sònrachadh oir graf eadar na h-earrainnean a[2i] agus a[2i+1], fa leth.
Chan eil fiosrachadh anns a’ chruth clàraidh seo a thaobh a bheil an graf air a stiùireadh (tha an dà roghainn comasach). Nuair a thathar a’ cleachdadh cruth nan digraph, thathas den bheachd gu bheil an oir air a stiùireadh bho a[2i] gu a[2i+1]. An seo agus gu h-ìosal: airson grafaichean neo-stiùiridh, ma tha sin riatanach, faodar riatanasan òrdugh clàraidh vertices a chuir an sàs (mar eisimpleir, gum bi an vertex le luach nas ìsle na h-àireimh a chaidh a shònrachadh dha a’ tighinn an toiseach).
Ann an C ++, tha e ciallach vectar faisg air làimh a shònrachadh a’ cleachdadh std :: vector, mar sin ainm an structair dàta seo.
Cùis (a2): graf neo-chuideachail, tha cuideaman iomall nan sèimhean
A rèir an t-samhlachais le cùis (a1), canaidh sinn an vectar faisg air làimh airson graf le cuideam le cuideaman iomall iomlanachd seata òrdaichte (sreath fiùghantach) de àireamhan (a[3i], a[3i+1], a[3i+2], ..., far a bheil i air a h-àireamhachadh c 0), far a bheil gach “triplet” de dh’ àireamhan a[3i], a[3i+1], a[3i+2] a’ sònrachadh iomall a’ ghraf eadar vertices le àireamh a[3i] agus a[3i+1], fa leth, agus is e an luach a [3i+2] cuideam an oir seo. Faodar graf mar seo a stiùireadh cuideachd no nach eil.
Cùis (b): graf gun chuideam, cuideaman oir neo-iomlan
Leis gu bheil e do-dhèanta eileamaidean heterogeneous a stòradh ann an aon raon (vector), mar eisimpleir, tha e comasach na leanas a bhuileachadh. Tha an graf air a stòradh ann am paidhir vectaran, anns a bheil a’ chiad vectar na vectar faisg air a’ ghraf gun a bhith a’ sònrachadh na cuideaman, agus tha na cuideaman co-fhreagarrach anns an dàrna vectar (buileachadh comasach airson C ++: std ::paidhir ). Mar sin, airson oir a tha air a mhìneachadh le paidhir vertices fo chlàran-amais 2i, 2i + 1 den chiad vectar, bidh an cuideam co-ionann ris an eileamaid fo chlàr-innse i den dàrna vectar.
Uill, carson a tha seo riatanach?
Uill, bha ùghdar nan loidhnichean sin gu math feumail airson grunn dhuilgheadasan fhuasgladh. Uill, bho shealladh foirmeil, bidh na buannachdan a leanas ann:
- Tha an vectar faisg air làimh, mar structar “àireamhach” sam bith eile, gu math toinnte, a’ gabhail nas lugha de chuimhne na am matrix faisg air làimh (airson grafaichean gann), agus tha e an ìre mhath furasta a bhuileachadh.
- Faodar uinneanan a’ ghraf, ann am prionnsapal, a chomharrachadh le àireamhan àicheil cuideachd. Dè ma tha feum air a leithid de “chasg”?
- Faodaidh ioma-oirean agus ioma lùban a bhith ann an grafaichean, le cuideaman eadar-dhealaichte (dearbhach, àicheil, eadhon neoni). Chan eil cuingealachaidhean an seo.
- Faodaidh tu cuideachd feartan eadar-dhealaichte a shònrachadh gu oirean - ach airson barrachd air sin, faic earrann 4.
Ach, feumar aideachadh nach eil an “liosta” seo a’ ciallachadh ruigsinneachd luath air an oir. Agus an seo thig an t-Array Adjacency Associative gu teasairginn, a tha air a dheasbad gu h-ìosal.
3.2 Raon co-cheangail cheangail
Mar sin, ma tha ruigsinneachd air oir sònraichte, a chuideam agus feartan eile deatamach dhuinn, agus nach leig riatanasan cuimhne leinn am matrix faisg air làimh a chleachdadh, an uairsin smaoinichidh sinn air mar as urrainn dhuinn an vectar faisg air làimh atharrachadh gus an duilgheadas seo fhuasgladh. Mar sin, is e iomall a’ ghraf a th’ anns an iuchair, a dh’fhaodar a shònrachadh mar phaidhir shlàn-àireimh òrdaichte. Cò ris a tha seo coltach? Nach e iuchair a th’ ann ann an raon co-cheangail? Agus, ma tha, carson nach cuir sinn an gnìomh e? Leig leinn sreath ceangail a bhith againn far am bi gach iuchair - paidhir shlàn-àireimh òrdaichte - co-cheangailte ri luach - àireamh iomlan no fìor àireamh a tha a 'sònrachadh cuideam an oir. Ann an C ++, tha e ciallach an structar seo a chuir an gnìomh stèidhichte air an std :: mapa container (std :: mapa , int> or std ::mapa , double>), neo std ::multimap ma tha dùil ri ioma oir. Uill, tha structar againn airson grafaichean a stòradh a bheir suas nas lugha de chuimhne na structaran “matrix”, as urrainn grafaichean a mhìneachadh le ioma lùban is oirean, agus aig nach eil eadhon riatanasan teann airson neo-àicheil àireamhan vertex (chan eil fhios agam cò a tha feumach air seo, ach fhathast).
4. Tha structaran dàta làn, ach tha rudeigin a dhìth
Agus tha e fìor: nuair a bhios sinn a 'fuasgladh grunn dhuilgheadasan, is dòcha gum feum sinn cuid de fheartan a shònrachadh gu oir a' ghraf agus, mar sin, an stòradh. Ma tha e comasach na feartan sin a lughdachadh gu h-iomlan, tha e comasach an leithid de “ghrafaichean le feartan a bharrachd” a stòradh le bhith a’ cleachdadh dreachan leudaichte den vectar faisg air làimh agus an sreath ri taobh co-cheangail.
Mar sin, leig dhuinn graf gun cuideam a bhith againn, airson gach oir tha e riatanach a stòradh, mar eisimpleir, 2 fheartan a bharrachd air an sònrachadh le integers. Anns a’ chùis seo, tha e comasach an vectar faisg air làimh a mhìneachadh mar sheata òrdaichte chan ann de “chàraidean”, ach de “quartets” de shlàn-àireamhan (a[2i], a[2i+1], a[2i+2], a [2i+3]…), far am bi a[2i+2] agus a[2i+3] a’ dearbhadh feartan an oir fhreagarrach. Airson graf le cuideaman iomlan nan oirean, tha an òrdugh mar as trice coltach (is e an aon eadar-dhealachadh gum bi na buadhan a’ leantainn cuideam an oir agus gun tèid an sònrachadh leis na h-eileamaidean a[2i+3] agus a[2i+4] , agus thèid an oir fhèin a shònrachadh chan e 4, ach 5 àireamhan òrdaichte). Agus airson graf le cuideaman oir neo-iomlan, faodar na feartan a sgrìobhadh a-steach don phàirt gun cuideam aige.
Nuair a bhios tu a’ cleachdadh raon dlùth-cheangail ceangail airson grafaichean le cuideaman iomall iomlanachd, tha e comasach sònrachadh mar luach chan e aon àireamh, ach sreath (vector) de àireamhan a tha a’ sònrachadh, a bharrachd air cuideam oir, a h-uile càil eile a tha riatanach. feartan. Aig an aon àm, bidh mì-ghoireasachd ann an cùis cuideaman neo-iomlan an fheum air soidhne a shònrachadh le àireamh puing fleòdraidh (tha, is e mì-ghoireasachd a tha seo, ach mura h-eil uimhir de shoidhnichean mar sin ann, agus ma nì thu sin Na suidhich iad dùbailte “trom”, an uairsin is dòcha nach bi e dad). Tha seo a’ ciallachadh, ann an C++, gum faodar arrays co-cheangail leudaichte a mhìneachadh mar a leanas: std ::mapa , std::vector> neo std ::mapa , std ::vector, anns am bi a 'chiad luach anns an "prìomh-luach-vector" mar chuideam an oir, agus an uairsin tha na sònrachaidhean àireamhach de na feartan aige air an suidheachadh.
Tùsan:
Mu ghrafaichean agus algorithms san fharsaingeachd:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithms: togail agus mion-sgrùdadh, 2na deasachadh: Trans. bhon Bheurla - M.: Taigh Foillseachaidh Williams, 2011.
2. Harari Frank. Teòiridh graf. M.: Mir, 1973.
Aithisg an ùghdair air na h-aon fheartan vectar agus co-cheangail de cheanglaichean:
3. Chernoukhov S.A. Vector faisg air làimh agus raon co-cheangail mar dhòighean air grafaichean a riochdachadh agus a stòradh / SA Chernouhov. Vector faisg air làimh agus mapa ri thaobh mar structaran dàta gus graf a riochdachadh // Cruinneachadh de artaigilean na Co-labhairt Saidheansail is Practaigeach Eadar-nàiseanta “Duilgheadasan le buileachadh toraidhean leasachaidhean ùr-ghnàthach agus dòighean air am fuasgladh” (Saratov, Sultain 14.09.2019, 2019). - Sterlitamak: AMI, 65, td. 69-XNUMX
Stòran feumail air-loidhne air a’ chuspair:
4.
5.
Source: www.habr.com