Dia duit gach duine.
Sa nóta seo, chinn mé liosta a dhéanamh de na príomhstruchtúir sonraí a úsáidtear chun graif a stóráil san eolaíocht ríomhaireachta, agus labhróidh mé freisin faoi chúpla struchtúr eile dá leithéid a “criostalaithe” dom ar bhealach éigin.
Mar sin, déanaimis tosú. Ach ní ón tús - is dóigh liom go bhfuil a fhios againn go léir cheana féin cad is graf ann agus cad iad (dírithe, neamhdhírithe, ualaithe, neamhualaithe, le imill agus lúb iolracha nó gan iad).
Mar sin, a ligean ar dul. Cad iad na roghanna atá againn maidir le struchtúir sonraí le haghaidh “stóráil graif”?
1. Struchtúir sonraí maitrís
1.1 Maitrís cóngarachta. Is maitrís í an mhaitrís cóngarachta ina gcomhfhreagraíonn na ceannteidil rónna agus colúin d'uimhreacha rinn an ghraif, agus déantar luach gach eilimint dá chuid a(i,j) a chinneadh ag láithreacht nó neamhláithreacht imill idir rinn i agus j (is léir go mbeidh maitrís den sórt sin siméadrach do ghraf neamhdhírithe, nó is féidir linn a chomhaontú go stórálfaimid gach luach os cionn an phríomhthrasnáin amháin). I gcás graif neamhualaithe, is féidir a(i,j) a shocrú de réir líon na n-imeall ó i go j (mura bhfuil imeall dá leithéid ann, ansin a(i,j) = 0), agus i gcás graif ualaithe, de réir an mheáchain freisin (meáchan iomlán) de na himill luaite.
1.2 maitrís minicíochta. Sa chás seo, stóráiltear ár ngraf freisin i dtábla ina bhfuil, mar riail, na huimhreacha sraitheanna ag freagairt d'uimhreacha a rinn, agus comhfhreagraíonn uimhreacha na gcolún d'imill réamh-uimhrithe. Má tá rinn agus ciumhais teagmhasach dá chéile, scríobhtar luach neamh-nialas sa chill chomhfhreagrach (do ghraif neamhdhírithe, scríobhtar 1 má tá an rinn agus an t-imeall teagmhasach, do ghraif dhírithe - "1" má tá an imeall “amach” ón rinn agus “-1” má “áirítear” ann (is furasta go leor cuimhneamh, mar is cosúil go bhfuil an comhartha “lúide” “san áireamh” san uimhir “-1”) freisin. Le haghaidh graif ualaithe, arís, in ionad 1 agus -1, is féidir leat meáchan iomlán an imeall a shonrú.
2. Struchtúir sonraí áirimh
2.1 Liosta cóngarachta. Bhuel, is cosúil go bhfuil gach rud simplí anseo. Is féidir, go ginearálta, gach rinn den ghraf a nascadh le haon struchtúr áirimh (liosta, veicteoir, eagar, ...), a stórálfaidh uimhreacha na rinn uile in aice leis an gceann a thugtar. Maidir le graif dhírithe, ní chuirfimid le liosta dá leithéid ach na rinn a bhfuil imeall “stiúrtha” orthu ó rinn gné. I gcás graif ualaithe beidh an cur i bhfeidhm níos casta.
2.2 Liosta easnacha. Struchtúr sonraí coitianta go leor. Is éard atá i liosta na n-imill, mar a insíonn Captaen Obviousness dúinn, liosta imill an ghraif, agus tá gach ceann acu sonraithe ag an rinn tosaigh, an rinn deiridh (do ghraif neamhdhírithe níl an t-ordú tábhachtach anseo, cé gur féidir leat a aontú. rialacha éagsúla a úsáid, mar shampla, na rinn a shonrú in ord méadaitheach) agus meáchan (do ghraif ualaithe amháin).
Is féidir leat breathnú ar na liostaí maitrís atá liostaithe thuas go mion (agus le léaráidí), mar shampla, .
2.3 Eagar cóngarachta. Ní hé an struchtúr is coitianta. Ag an gcroílár, is foirm de liostaí cóngarachta “pacála” é in aon struchtúr áireamhachta amháin (eagar, veicteoir). Sa chéad n (de réir líon rinn an ghraif) tá na hinnéacsanna tosaigh den eagar céanna sna heilimintí den sórt sin d'eagar, ag tosú as a scríobhtar gach rinn in aice leis an gceann tugtha i ndiaidh a chéile.
Anseo fuair mé an míniú is sothuigthe (dom féin):
3. Veicteoir Cóngarachta agus Eagar Cóngarachta Comhtháite
Iompaigh sé amach go bhfuil an t-údar de na línte, gan a bheith ina ríomhchláraitheoir gairmiúil, ach a dhéileáil go tréimhsiúil le graif, is minic a dhéileáil le liostaí de imill. Go deimhin, tá sé áisiúil má tá lúba agus imill iolracha ag an ngraf. Agus mar sin, agus liostaí clasaiceacha na n-imeall á bhforbairt, tá sé i gceist agam aird a thabhairt ar a “forbairt/brainse/modhnú/sóchán”, eadhon: an veicteoir cóngarachta agus an t-eagar cóngarachta comhlachaithe.
3.1 Veicteoir tadhlach
Cás (a1): graf neamhualaithe
Glaoimid ar veicteoir cóngarachta do ghraf neamhualaithe tacar ordaithe de chomhlíon slánuimhreacha (a[2i], a[2i+1],..., áit a bhfuil i uimhrithe c 0), ina bhfuil gach péire uimhreacha is a[2i], sonraíonn a[2i+1 ] imeall graf idir na rinn a[2i] agus a[2i+1], faoi seach.
Níl faisnéis san fhormáid taifeadta seo maidir le cé acu an bhfuil an graf dírithe (tá an dá rogha indéanta). Nuair a bhíonn formáid na déghraf in úsáid, meastar go bhfuil an t-imeall dírithe ó a[2i] go a[2i+1]. Anseo agus thíos: maidir le graif neamhdhírithe, más gá, is féidir ceanglais maidir le hord na rinn taifeadta a chur i bhfeidhm (mar shampla, gurb é an rinn a bhfuil luach níos ísle na huimhreach a thugtar dó a thagann ar dtús).
In C++, tá sé inmholta veicteoir cóngarachta a shonrú ag baint úsáide as std::vector, mar sin ainm an struchtúir sonraí seo.
Cás (a2): graf neamhualaithe, is slánuimhir iad meáchain imeall
De réir analaí le cás (a1), tugaimid an veicteoir cóngarachta do ghraf ualaithe le meáchain chiumhais an tslánuimhir tacar ordaithe (eagar dinimiciúil) uimhreacha (a[3i], a[3i+1], a[3i+2], ..., áit a bhfuil i uimhrithe c 0), áit a sonraíonn gach “tríarán” d'uimhreacha a[3i], a[3i+1], a[3i+2] imeall an ghraif idir na rinn a bhfuil a[3i] agus a[3i+1], faoi seach, agus is é an luach a [3i+2] meáchan an chiumhais seo. Is féidir graf den sórt sin a threorú nó nach bhfuil.
Cás (b): graf neamhualaithe, meáchain imeall neamhshlánuimhir
Ós rud é go bhfuil sé dodhéanta eilimintí ilchineálacha a stóráil in aon eagar (veicteoir), mar shampla, is féidir an cur i bhfeidhm seo a leanas a dhéanamh. Stóráiltear an graf i bpéire veicteoirí, inarb é an chéad veicteoir veicteoir cóngarachta an ghraif gan na meáchain a shonrú, agus tá na meáchain chomhfhreagracha sa dara veicteoir (feidhmiú féideartha do C++: std ::péire ). Mar sin, i gcás ciumhais atá sainmhínithe ag péire rinn faoi innéacsanna 2i, 2i+1 den chéad veicteoir, beidh an meáchan cothrom leis an dúil faoi innéacs i den dara veicteoir.
Bhuel, cén fáth go bhfuil sé seo riachtanach?
Bhuel, fuair údar na línte seo an-úsáideach chun roinnt fadhbanna a réiteach. Bhuel, ó thaobh foirmiúil de, beidh na buntáistí seo a leanas:
- Tá an veicteoir cóngarachta, cosúil le haon struchtúr “áirimh” eile sách dlúth, glacann sé níos lú cuimhne ná an mhaitrís cóngarachta (do ghraif tanaí), agus tá sé sách éasca é a chur i bhfeidhm.
- Is féidir rinn an ghraif, i bprionsabal, a mharcáil freisin le huimhreacha diúltacha. Cad a tharlóidh má tá a leithéid de “shaobhadh” de dhíth?
- Is féidir imill iolracha agus lúba iolracha a bheith sna graif, le meáchain éagsúla (dearfach, diúltach, fiú nialas). Níl aon srianta anseo.
- Is féidir leat airíonna éagsúla a shannadh d’imill freisin - ach le haghaidh tuilleadh air sin, féach cuid 4.
Ní mór a admháil, áfach, nach gciallaíonn an “liosta” seo rochtain thapa ar an imeall. Agus is anseo a thagann an Eagrán Cóngarachta Comhthiomsaitheach chun tarrthála, a phléitear thíos.
3.2 Eagar cóngarachta comhlach
Mar sin, má tá rochtain ar chiumhais ar leith, a mheáchan agus airíonna eile ríthábhachtach dúinn, agus nach ligeann riachtanais chuimhne dúinn an maitrís cóngarachta a úsáid, ansin déanaimis smaoineamh ar conas is féidir linn an veicteoir cóngarachta a athrú chun an fhadhb seo a réiteach. Mar sin, is imeall an ghraif an eochair, ar féidir é a shonrú mar phéire ordaithe slánuimhreacha. Cén chuma atá air seo? Nach eochair é in eagar comhthiomsaitheach? Agus, más ea, cén fáth nach gcuirimid i bhfeidhm é? Bíodh eagar comhthiomsaitheach againn ina mbeidh baint ag gach eochair - péire ordaithe slánuimhreacha - le luach - slánuimhir nó réaduimhir a shonraíonn meáchan an chiumhais. In C++, moltar an struchtúr seo a chur i bhfeidhm bunaithe ar an gcoimeádán std::map (std::mapa , int> nó std::mapa , dúbailte>), nó std::multimaap má táthar ag súil le himill iolracha. Bhuel, tá struchtúr againn chun graif a stóráil a thógann suas níos lú cuimhne ná struchtúir “maitrís”, ar féidir leo graif a shainiú le lúba agus imill iolracha, agus nach bhfuil ceanglais dhian aige fiú maidir le neamh-dhiúltacht uimhreacha rinn (níl a fhios agam cé atá de dhíth air seo, ach fós).
4. Tá struchtúir sonraí iomlán, ach tá rud éigin ar iarraidh
Agus tá sé fíor: nuair a bhíonn roinnt fadhbanna á réiteach, b'fhéidir go gcaithfimid roinnt tréithe a shannadh d'imill an ghraif agus, dá réir sin, iad a stóráil. Más féidir na gnéithe seo a laghdú go slánuimhreacha gan athbhrí, is féidir “graif le gnéithe breise” den sórt sin a stóráil trí leas a bhaint as leaganacha leathnaithe den veicteoir cóngarachta agus den eagar comhthaobhachta cóngarachta.
Mar sin, lig dúinn graf neamhualaithe, le haghaidh gach imeall a bhfuil sé riachtanach a stóráil, mar shampla, 2 gnéithe breise atá sonraithe ag slánuimhreacha. Sa chás seo, is féidir a veicteoir cóngarachta a shainiú mar thacar ordaithe ní “péirí”, ach “ceathairéad” de shlánuimhreacha (a[2i], a[2i+1], a[2i+2], a [2i+3]…), áit a gcinnfidh a[2i+2] agus a[2i+3] tréithe an chiumhais chomhfhreagraigh. Maidir le graf a bhfuil meáchan slánuimhreacha imill aige, bíonn an t-ord comhchosúil go ginearálta (is é an t-aon difríocht a bheidh ann ná go leanfaidh na tréithe meáchan an chiumhais agus go sonrófar iad leis na heilimintí a[2i+3] agus a[2i+4] , agus ní shonrófar an imeall féin 4, ach 5 uimhreacha ordaithe). Agus le haghaidh graf le meáchain imeall neamh-shlánuimhir, is féidir na gnéithe a scríobh ina chomhpháirt neamhualaithe.
Agus eagar cóngarachta in úsáid le haghaidh graif a bhfuil meáchain chiumhais an tslánuimhir acu, is féidir a shonrú mar luach, ní uimhir amháin, ach eagar (veicteoir) uimhreacha a shonraíonn, chomh maith le meáchan imeall, gach rud eile is gá. gnéithe. Ag an am céanna, beidh míchaoithiúlacht i gcás meáchain neamh-sláine an gá atá le comhartha a shonrú le uimhir snámhphointe (tá, is míchaoithiúlacht é seo, ach mura bhfuil an oiread sin comharthaí den sórt sin ann, agus má dhéanann tú. Ná leag siad ró-dhúbailte “tricky”, ansin d'fhéadfadh sé a bheith rud ar bith). Ciallaíonn sé seo gur féidir eagair sínte cóngarachta i C++ a shainiú mar seo a leanas: std::mapa , std::veicteoir> nó std::mapa , std::veicteoir, ina mbeidh an chéad luach sa “veicteoir eochrach-luacha” mar mheáchan an chiumhais, agus ansin tá sonrúcháin uimhriúla a saintréithe suite.
Litríocht:
Maidir le graif agus halgartaim go ginearálta:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algartam: tógáil agus anailís, 2ú eagrán: Transl. ón mBéarla – M.: Teach Foilsitheoireachta Williams, 2011.
2. Harari Frank. Teoiric graf. M.: Mir, 1973.
Tuairisc an údair ar na veicteora céanna seo agus ar na naisc chomhthiomsaitheacha chéanna:
3. Chernoukhov S.A. Veicteoir tadhlach agus eagar comhghaolmhaireachta mar bhealaí chun graif a léiriú agus a stóráil / SA Chernouhov. Veicteoir cóngarachta agus léarscáil cóngarachta mar struchtúir sonraí chun graf a léiriú // Bailiúchán d’alt den Chomhdháil Idirnáisiúnta Eolaíoch agus Phraiticiúil “Fadhbanna a bhaineann le torthaí forbairtí nuálaíocha a chur i bhfeidhm agus bealaí chun iad a réiteach” (Saratov, 14.09.2019 Meán Fómhair, 2019). – Sterlitamak: AMI, 65, lch. 69-XNUMX
Foinsí úsáideacha ar líne ar an ábhar:
4.
5.
Foinse: will.com