Helo pawb
Yn y nodyn hwn, penderfynais restru'r prif strwythurau data a ddefnyddir i storio graffiau mewn cyfrifiadureg, a byddaf hefyd yn siarad am ychydig yn fwy o strwythurau o'r fath sydd rywsut yn “grisialu” i mi.
Felly, gadewch i ni ddechrau. Ond nid o'r cychwyn cyntaf - rwy'n meddwl ein bod ni i gyd eisoes yn gwybod beth yw graff a beth ydyn nhw (cyfeirio, heb ei gyfeirio, wedi'i bwysoli, heb ei bwysoli, gyda neu heb ymylon a dolenni lluosog).
Felly, gadewch i ni fynd. Pa opsiynau ar gyfer strwythurau data ar gyfer “storio graffiau” sydd gennym ni?
1. Strwythurau data matrics
1.1 Matrics cyfagosrwydd. Mae'r matrics cyfagosrwydd yn fatrics lle mae'r penawdau rhes a cholofn yn cyfateb i rifau fertigau'r graff, ac mae gwerth pob un o'i elfennau a(i,j) yn cael ei bennu gan bresenoldeb neu absenoldeb ymylon rhwng fertigau i a j (mae'n amlwg y bydd matrics o'r fath yn gymesur ar gyfer graff heb ei gyfeirio, neu gallwn gytuno ein bod yn storio pob gwerth yn unig uwchlaw'r prif groeslin). Ar gyfer graffiau heb eu pwysoli, gellir gosod a(i,j) yn ôl nifer yr ymylon o i i j (os nad oes ymyl o'r fath, yna a(i,j) = 0), ac ar gyfer graffiau pwysol, hefyd yn ôl y pwysau (cyfanswm pwysau) yr ymylon a grybwyllwyd.
1.2 Matrics achosion. Yn yr achos hwn, mae ein graff hefyd yn cael ei storio mewn tabl lle, fel rheol, mae'r rhifau rhes yn cyfateb i rifau ei fertigau, ac mae rhifau'r colofnau yn cyfateb i ymylon sydd wedi'u rhifo ymlaen llaw. Os yw fertig ac ymyl yn digwydd i'w gilydd, yna ysgrifennir gwerth di-sero yn y gell gyfatebol (ar gyfer graffiau heb eu cyfeirio, ysgrifennir 1 os yw'r fertig a'r ymyl yn anwastad, ar gyfer graffiau â gogwydd - "1" os yw'r ymyl “allanfa” o’r fertig a “-1” os yw’n “cynnwys” ynddo (mae’n ddigon hawdd cofio, oherwydd mae’n ymddangos bod yr arwydd “minws” hefyd wedi ei “gynnwys” yn y rhif “-1”). Ar gyfer graffiau pwysol, eto, yn lle 1 a -1, gallwch chi nodi cyfanswm pwysau'r ymyl.
2. Strwythurau data cyfrifo
2.1 Rhestr cyffiniau. Wel, mae popeth yn ymddangos yn syml yma. Yn gyffredinol, gall pob fertig o'r graff fod yn gysylltiedig ag unrhyw strwythur cyfrifo (rhestr, fector, arae, ...), a fydd yn storio rhifau'r holl fertigau wrth ymyl yr un a roddir. Ar gyfer graffiau cyfeiriedig, byddwn yn ychwanegu at restr o'r fath dim ond y fertigau hynny y mae ymyl “cyfeirio” iddynt o fertig nodwedd. Ar gyfer graffiau pwysol, bydd y gweithrediad yn fwy cymhleth.
2.2 Rhestr o asennau. Strwythur data eithaf poblogaidd. Mae'r rhestr ymylon, fel y mae Capten Obviousness yn ei ddweud wrthym, mewn gwirionedd yn rhestr o ymylon y graff, pob un ohonynt wedi'i nodi gan y fertig cychwyn, y fertig sy'n dod i ben (ar gyfer graffiau heb eu cyfeirio nid yw'r drefn yn bwysig yma, er ar gyfer uno gallwch chi defnyddio rheolau amrywiol, er enghraifft, pennu'r fertigau yn nhrefn cynyddu) a phwysau (ar gyfer graffiau pwysol yn unig).
Gallwch edrych ar y rhestrau matrics a restrir uchod yn fwy manwl (a chyda darluniau), er enghraifft, .
2.3 Arae cyfagos. Nid y strwythur mwyaf cyffredin. Yn greiddiol iddo, mae'n fath o “bacio” rhestrau cyfagosrwydd yn un strwythur cyfrifo (arae, fector). Mae elfennau n cyntaf (yn ôl nifer fertigau'r graff) o arae o'r fath yn cynnwys mynegeion cychwynol yr un arae, gan ddechrau o'r hyn y mae pob fertig gyferbyn â'r un a roddir wedi'i ysgrifennu mewn rhes.
Yma cefais yr esboniad mwyaf dealladwy (i mi fy hun):
3. Fector Cyfagos ac Arae Cyfagosrwydd Cysylltiol
Mae'n troi allan bod awdur y llinellau hyn, nid yn rhaglennydd proffesiynol, ond sy'n delio o bryd i'w gilydd gyda graffiau, yn fwyaf aml yn delio â rhestrau o ymylon. Yn wir, mae'n gyfleus os oes gan y graff ddolenni ac ymylon lluosog. Ac felly, wrth ddatblygu’r rhestrau clasurol o ymylon, rwy’n cynnig rhoi sylw i’w “datblygiad/cangen/addasiad/treiglad”, sef: y fector cyfagosrwydd a’r arae cyfagosrwydd cysylltiadol.
3.1 Fector cyfagosrwydd
Achos (a1): graff heb ei bwysoli
Byddwn yn galw fector cyfagosrwydd ar gyfer graff heb ei bwysoli yn set drefnus o eilrif o gyfanrifau (a[2i], a[2i+1],..., lle mae i wedi'i rifo c 0), lle mae pob pâr o rifau yw a[2i], mae a[2i+1 ] yn pennu ymyl graff rhwng y fertigau a[2i] ac a[2i+1], yn ôl eu trefn.
Nid yw'r fformat recordio hwn yn cynnwys gwybodaeth ynghylch a yw'r graff wedi'i gyfeirio (mae'r ddau opsiwn yn bosibl). Wrth ddefnyddio'r fformat deugraff, ystyrir bod yr ymyl wedi'i gyfeirio o a[2i] i a[2i+1]. Yma ac isod: ar gyfer graffiau heb eu cyfeirio, os oes angen, gellir cymhwyso'r gofynion ar gyfer trefn y fertigau cofnodi (er enghraifft, mai'r fertig â gwerth is y nifer a neilltuwyd iddo sy'n dod gyntaf).
Yn C++, fe'ch cynghorir i nodi fector cyfagosrwydd gan ddefnyddio std::vector, sy'n esbonio enw'r strwythur data hwn.
Achos (a2): graff heb ei bwysoli, pwysau ymyl yn gyfanrif
Drwy gyfatebiaeth â chas (a1), rydyn ni'n galw'r fector cyfagosrwydd ar gyfer graff pwysol gyda phwysau ymyl cyfanrif yn set drefnus (arae deinamig) o rifau (a[3i], a[3i+1], a[3i+2], ..., lle mae i wedi'i rifo c 0), lle mae pob “tripled” o rifau a[3i], a[3i+1], a[3i+2] yn pennu ymyl y graff rhwng fertigau wedi'u rhifo a[3i] ac a[3i+1], yn y drefn honno, a'r gwerth a [3i+2] yw pwysau'r ymyl hwn. Gall graff o'r fath hefyd gael ei gyfeirio neu beidio.
Achos (b): graff heb ei bwysoli, pwysau ymyl nad yw'n gyfanrif
Gan ei bod yn amhosibl storio elfennau heterogenaidd mewn un arae (fector), er enghraifft, mae'r gweithredu canlynol yn bosibl. Mae'r graff yn cael ei storio mewn pâr o fectorau, lle mae'r fector cyntaf yn fector cyfagosrwydd y graff heb nodi'r pwysau, ac mae'r ail fector yn cynnwys y pwysau cyfatebol (gweithrediad posibl ar gyfer C++: std ::pair ). Felly, ar gyfer ymyl a ddiffinnir gan bâr o fertigau o dan fynegeion 2i, 2i+1 y fector cyntaf, bydd y pwysau yn hafal i'r elfen o dan fynegai i yr ail fector.
Wel, pam mae hyn yn angenrheidiol?
Wel, roedd awdur y llinellau hyn yn ei chael hi'n eithaf defnyddiol ar gyfer datrys nifer o broblemau. Wel, o safbwynt ffurfiol, bydd y manteision canlynol:
- Mae'r fector cyfagosrwydd, fel unrhyw strwythur “cyfrifol” arall, yn eithaf cryno, yn cymryd llai o gof na'r matrics cyfagosrwydd (ar gyfer graffiau gwasgaredig), ac mae'n gymharol hawdd i'w weithredu.
- Gall fertigau'r graff, mewn egwyddor, hefyd gael eu marcio â rhifau negatif. Beth os oes angen “gwyrdroi” o'r fath?
- Gall graffiau gynnwys ymylon lluosog a dolenni lluosog, gyda phwysau gwahanol (cadarnhaol, negyddol, hyd yn oed sero). Nid oes unrhyw gyfyngiadau yma.
- Gallwch hefyd aseinio gwahanol briodweddau i ymylon - ond am ragor ar hynny, gweler adran 4.
Fodd bynnag, rhaid cyfaddef nad yw'r “rhestr” hon yn awgrymu mynediad cyflym i'r ymyl. Ac yma daw'r Arae Cyfagosrwydd Cyswllt i'r adwy, a drafodir isod.
3.2 Arae cyfagosrwydd cysylltiadol
Felly, os yw mynediad i ymyl penodol, ei bwysau a phriodweddau eraill yn hanfodol i ni, ac nad yw gofynion cof yn caniatáu inni ddefnyddio'r matrics cyfagosrwydd, yna gadewch i ni feddwl sut y gallwn newid y fector cyfagosrwydd i ddatrys y broblem hon. Felly, ymyl y graff yw'r allwedd, y gellir ei nodi fel pâr trefnedig o gyfanrifau. Sut olwg sydd ar hwn? Onid yw'n allwedd mewn arae cysylltiadol? Ac, os felly, pam na wnawn ni ei roi ar waith? Gadewch inni gael arae cysylltiadol lle bydd pob allwedd - pâr trefnedig o gyfanrifau - yn gysylltiedig â gwerth - cyfanrif neu rif real sy'n pennu pwysau'r ymyl. Yn C++, fe'ch cynghorir i weithredu'r strwythur hwn yn seiliedig ar y cynhwysydd std::map (std::map , int> neu std::map , dwbl>), neu std::multimap os disgwylir ymylon lluosog. Wel, mae gennym strwythur ar gyfer storio graffiau sy'n cymryd llai o gof na strwythurau “matrics”, sy'n gallu diffinio graffiau â dolenni ac ymylon lluosog, ac nid oes ganddo hyd yn oed ofynion llym ar gyfer nad yw rhifau fertig yn negyddol (ni wn pwy sydd angen hwn, ond dal).
4. Mae strwythurau data yn llawn, ond mae rhywbeth ar goll
Ac mae'n wir: wrth ddatrys nifer o broblemau, efallai y bydd angen i ni aseinio rhai nodweddion i ymylon y graff ac, yn unol â hynny, eu storio. Os yw’n bosibl lleihau’r nodweddion hyn yn gyfanrifau yn ddiamwys, yna mae’n bosibl storio “graffiau gyda nodweddion ychwanegol” o’r fath gan ddefnyddio fersiynau estynedig o’r fector cyfagosrwydd a’r arae gyfagosrwydd cysylltiadol.
Felly, gadewch inni gael graff heb ei bwysoli, ar gyfer pob ymyl y mae angen storio, er enghraifft, 2 nodwedd ychwanegol a bennir gan gyfanrifau. Yn yr achos hwn, mae modd diffinio ei fector cyfagosrwydd fel set drefnus nid o “barau”, ond o “bedwarawd” o gyfanrifau (a[2i], a[2i+1], a[2i+2], a [2i+3]…), lle bydd a[2i+2] ac a[2i+3] yn pennu nodweddion yr ymyl cyfatebol. Ar gyfer graff gyda phwysau cyfanrif o ymylon, mae'r drefn yn debyg ar y cyfan (yr unig wahaniaeth fydd y bydd y priodoleddau'n dilyn pwysau'r ymyl ac yn cael eu pennu gan yr elfennau a[2i+3] ac a[2i+4] , a bydd yr ymyl ei hun yn cael ei nodi nid 4, ond 5 rhif archeb). Ac ar gyfer graff gyda phwysau ymyl nad yw'n gyfanrif, gellir ysgrifennu'r nodweddion yn ei gydran heb ei phwysoli.
Wrth ddefnyddio aráe cyfagosrwydd cysylltiadol ar gyfer graffiau gyda phwysau ymyl cyfanrif, mae'n bosibl nodi fel gwerth nid un rhif, ond arae (fector) o rifau sy'n nodi, yn ogystal â phwysau ymyl, ei holl angenrheidiol eraill. Nodweddion. Ar yr un pryd, anghyfleustra ar gyfer pwysau nad ydynt yn gyfanrif fydd yr angen i nodi arwydd gyda rhif pwynt arnawf (ie, mae hyn yn anghyfleustra, ond os nad oes cymaint o arwyddion o'r fath, ac os gwnewch hynny Peidiwch â'u gosod yn ddwbl rhy “anodd”, yna efallai nad yw'n ddim). Mae hyn yn golygu y gellir diffinio araeau cyfagosrwydd cysylltiadol estynedig yn C++ fel a ganlyn: std::map , std::vector> neu std::map , std::vector, lle bydd y gwerth cyntaf yn y “fector gwerth allweddol” yn bwysau'r ymyl, ac yna mae dynodiadau rhifiadol ei nodweddion wedi'u lleoli.
Llenyddiaeth:
Ynglŷn â graffiau ac algorithmau yn gyffredinol:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithmau: adeiladu a dadansoddi, 2il argraffiad: Traws. o'r Saesneg – M.: Tŷ Cyhoeddi Williams, 2011.
2. Harari Frank. Theori graff. M.: Mir, 1973.
Adroddiad yr awdur am yr un fector a'r amrywiaeth cysylltiadol hyn o gymariaethau:
3. Chernoukhov S.A. Fector cyfochrog ac arae cyfagosrwydd cysylltiadol fel ffyrdd o gynrychioli a storio graffiau / SA Chernouhov. Fector cyfagos a map cyfagosrwydd fel strwythurau data i gynrychioli graff // Casgliad o erthyglau'r Gynhadledd Wyddonol ac Ymarferol Ryngwladol “Problemau gweithredu canlyniadau datblygiadau arloesol a ffyrdd o'u datrys” (Saratov, Medi 14.09.2019, 2019). – Sterlitamak: AMI, 65, t. 69-XNUMX
Ffynonellau defnyddiol ar-lein ar y pwnc:
4.
5.
Ffynhonnell: hab.com