Përshëndetje të gjithëve.
Në këtë shënim, kam vendosur të rendis strukturat kryesore të të dhënave që përdoren për ruajtjen e grafikëve në informatikë, si dhe do të flas për disa struktura të tjera që në një farë mënyre janë "kristalizuar" vetvetiu.
Pra, le tĂ« fillojmĂ«. Por jo nga fillimi â mendoj se çfarĂ« Ă«shtĂ« njĂ« grafik dhe cilat janĂ« llojet e tij (tĂ« orientuar, tĂ« paorientuar, tĂ« peshuar, tĂ« papeshuar, me brinjĂ« shumĂ«fishe dhe kitapĂ« ose pa to), ne tashmĂ« e dimĂ«.
Pra, le të shkojmë. Cilat janë mundësitë e strukturave të të dhënave për "ruajtjen e grafikëve" që kemi?
1. Strukturat e të dhënave matricore
1.1 Matrica e fqinjĂ«sisĂ«. Matrica e afĂ«rsisĂ« pĂ«rfaqĂ«son njĂ« matricĂ« ku titujt e rreshtave dhe kolonave korrespondojnĂ« me numrat e pikave tĂ« grafit, dhe vetĂ« vlera e çdo elementi tĂ« saj a(i,j) pĂ«rcaktohet nga prania ose mungesa e nyjeve mes pikave i dhe j (Ă«shtĂ« e qartĂ« se pĂ«r grafet e paorientuara njĂ« matricĂ« e tillĂ« do tĂ« jetĂ« simetrike, ose mund tĂ« rahemi dakord qĂ« tĂ« gjitha vlerat t'i ruajmĂ« vetĂ«m mbi diagonalĂ«n kryesore). pĂ«r grafet e pa peshuara, a(i,j) mund tĂ« jepet me numrin e nyjeve nga i nĂ« j (nĂ«se nuk ka njĂ« nyje tĂ« tillĂ«, atĂ«herĂ« a(i,j) = 0), dhe pĂ«r grafet e peshuara gjithashtu â me peshĂ«n (peshĂ«n totale) e nyjeve tĂ« pĂ«rmendura.
1.2 Matrica e incidentĂ«s. NĂ« kĂ«tĂ« rast, grafiku ynĂ« ruhet gjithashtu nĂ« njĂ« tabelĂ«, ku zakonisht numrat e rreshtave pĂ«rputhen me numrat e majave tĂ« tij, ndĂ«rsa numrat e kolonave pĂ«rputhen me anĂ«t qĂ« janĂ« numĂ«ruar paraprakisht. NĂ«se njĂ« majĂ« dhe njĂ« anĂ« janĂ« incidente me njĂ«ra-tjetrĂ«n, atĂ«herĂ« nĂ« qeliza pĂ«rkatĂ«se regjistrohet njĂ« vlerĂ« e pazerosuar (pĂ«r grafĂ«t e paorientuar regjistrohet 1 nĂ« rastin e incidentĂ«s ndĂ«rmjet majĂ«s dhe anĂ«s, pĂ«r grafĂ«t e orientuar â â1â nĂ«se anĂ« âdilâ nga maja dhe â-1â nĂ«se ajo âhyâ nĂ« tĂ« (kaq e lehtĂ« Ă«shtĂ« tĂ« kujtohet, sepse shenja âminusâ gjithashtu siç duket âhyâ nĂ« numrin â-1â). PĂ«r grafĂ«t me peshĂ«, sĂ«rish mund tĂ« citohet pesha totale e anĂ«s nĂ« vend tĂ« 1 dhe -1.
2. Strukturat e të dhënave enumeruese
2.1 Lista e fqinjĂ«sisĂ«. KĂ«tu duket se Ă«shtĂ« shumĂ« e thjeshtĂ«. Ădo majĂ« e grafit mund, nĂ« pĂ«rgjithĂ«si, t'i pĂ«rputhet çdo strukture enumeruese (listĂ«, vektor, array, âŠ), nĂ« tĂ« cilĂ«n do tĂ« ruhen numrat e tĂ« gjitha majave fqinje tĂ« dhĂ«nĂ«s. PĂ«r grafĂ«t e orientuar do tĂ« regjistrojmĂ« nĂ« njĂ« listĂ« tĂ« tillĂ« vetĂ«m ato majĂ« nĂ« tĂ« cilat ka njĂ« anĂ« "me drejtim" nga maja e njohur. PĂ«r grafĂ«t me peshĂ«, realizimi do tĂ« jetĂ« mĂ« i komplikuar.
2.2 Lista e skajeveve. Një strukturë të dhënash mjaft të njohur. Lista e skajeve, siç na tregon Kapitani i Dukshme, përfaqëson pikërisht listën e skajeve të një grafoje, secili prej të cilëve përcaktohet nga skaji fillestar, skaji përfundimtar (për grafet e pa orientuara, rendi këtu nuk ka rëndësi, megjithatë për të unifikuar mund të përdoren rregulla të ndryshme, për shembull, të përcaktohet skajet në rendin e rritjes) dhe pesha (vetëm për grafet me peshë).
Mund të shikoni më shumë për listat-matricë të përmendura më lart (dhe me ilustrazione), për shembull, .
2.3 Array i fqinjësisë. Një strukturë e cila nuk është aq e zakonshme. Në thelb, ajo përfaqëson një formë 'paketimi' të listave të fqinjësisë në një strukturë të njëpasnjëshme (array, vektori). Elementet e para n (sipërfaqja e numrit të skajeve në graf) të këtij array përmbajnë indekset fillestare të këtij array, duke filluar nga ku janë regjistruar të gjithë skajet e afërta me këtë skaj.
Këtu kam gjetur shpjegimin më të kuptueshëm (për vete):
3. Vektori i fqinjësisë dhe Harku Asociativ i fqinjësisë
Ka ndodhi që autori i këtyre rreshtave, ndonëse nuk është një programues profesionist, gjithsesi ka pasur rastësisht lidhje me grafë, kryesisht ka punuar me lista të skajeve. Në të vërtetë, është e dobishme nëse grafi ka cikle të shumta dhe skaje. Dhe tani, në vazhdim të listave klasike të skajeve, propozoj të kushtojmë vëmendje edhe zhvillimit, degëzimit, modifikimit apo mutation-it të tyre, domethënë: vektorit të fqinjësisë dhe asociasionit të asociasionit.
3.1 Vektori i fqinjësisë
Rasti (a1): graf i pa-peshuar
Ne do ta quajmĂ« vektor fqinjĂ«sie pĂ«r njĂ« graf tĂ« pa-peshuar njĂ« set tĂ« renditur me njĂ« numĂ«r tĂ« madh çift tĂ« numrave tĂ« plotĂ« (a[2i], a[2i+1],âŠ, ku i numĂ«rohet qĂ« nga 0), nĂ« tĂ« cilin çdo çift numrash a[2i], a[2i+1] pĂ«rcakton njĂ« skaj tĂ« grafit midis nyjeve a[2i] dhe a[2i+1] pĂ«rkatĂ«sisht.
Kjo format i shkruar nuk përmban informacion nëse grafi është i orientuar (të dy varianta janë të mundshme). Kur përdoret ky format për graf, merret që skaji është i orientuar nga a[2i] në a[2i+1]. Këtu dhe më tej: për grafët e paorientuar, mund të aplikohen kërkesa për rendin e shenimeve të kulmave (për shembull, që të parës i shkon kulmi me vlerën më të vogël të numrit të dhënë asaj).
Në C++, është e përshtatshme të përcaktohet vektori i fqinjësisë me std::vector, ndaj është zgjedhur ky emër për këtë strukturë të dhënash.
Rasti (a2): graf i paqartësuar, pesha e skajeve është e numërueshme.
Si në rastin (a1), do ta quajmë vektor fqinjësie për një graf të peshuar me pesha të skajeve numëruese, një grup i renditur (një varg dinamik) numërash (a[3i], a[3i+1], a[3i+2],..., ku i numeron nga 0), ku çdo "triple" numrash a[3i], a[3i+1], a[3i+2] përcakton një skaj grafi midis kulmave të numëruara a[3i] dhe a[3i+1], përkatësisht, ndërsa vlera a[3i+2] është pesha e këtij skaji. Ky graf gjithashtu mund të jetë i orientuar ose jo.
Rasti (b): graf i paqartësuar, pesha e skajeve nuk është numëruese.
Duke për faktin se në një masiv (vektor) nuk mund të ruhet elemente të ndryshme, është e mundur, për shembull, një realizim i tillë. Grafi ruhet në një çift vektorësh, ku vektori i parë është vektori i fqinjësisë së grafit pa treguar pesha, ndërsa vektori i dytë përmban peshat përkatëse (një realizim i mundshëm për C++: std::pair). Pra, për një brinjë, e cila përcaktohet nga një çift verticesh me indekse 2i, 2i+1 të vektorit të parë, pesha do të jetë e barabartë me elementin me indeks i të vektorit të dytë.
Po pse është e nevojshme kjo?
Epo, autorit të këtyre rreshtave për të zgjidhur një sërë problemesh kyç shfaqet mjaft i dobishëm. Nga një pikëpamje formale, do të ketë këto përparësi:
- Vektori i fqinjësisë, si çdo strukturë tjetër "treguese", është mjaft kompakt, zë më pak memorie se matrica e fqinjësisë (për grafet e shpërndara), dhe realizohet relativisht lehtë.
- Vertexet e grafit, në parim, mund të jenë të shënuara edhe me numra negativë. Ndoshta do të nevojitet një "devijim" i tillë.
- Grafët mund të përmbajnë shumë breza dhe shumë cikle, me pesha të ndryshme (pozitive, negative, madje zero). Nuk ka kufizime këtu.
- Për më tepër, brezat mund të kenë vetitë e ndryshme - por për këtë shihni pika 4.
Megjithatë, duhet të pranojmë se ky "listëk" nuk ofron qasje të shpejtë në breza. Dhe këtu vjen në ndihmë Mappa asocative e fqinjësisë, për të cilën do të flasim më poshtë.
3.2 Mappa asocative e fqinjësisë
Pra ndaj, nĂ«se pĂ«r ne Ă«shtĂ« thelbĂ«sore tĂ« kemi akses nĂ« njĂ« brinjĂ« tĂ« caktuar, pesha e saj dhe pronarĂ« tĂ« tjerĂ«, dhe kĂ«rkesat pĂ«r memorie nuk na lejojnĂ« tĂ« pĂ«rdorim njĂ« matricĂ« fqinjĂ«sie, le tĂ« mendojmĂ« se si mund ta ndryshojmĂ« vektorin e fqinjĂ«sisĂ« pĂ«r tĂ« zgjidhur kĂ«tĂ« problem. Pra, çelĂ«si Ă«shtĂ« brinja e grafit, e cila mund tĂ« pĂ«rshkruhet si njĂ« palĂ« tĂ« renditur numrash tĂ« tĂ«rĂ«. ĂfarĂ« iu ngjan kĂ«saj? A nuk Ă«shtĂ« çelĂ«si nĂ« njĂ« varg asociativ? Dhe nĂ«se Ă«shtĂ« kĂ«shtu, pse tĂ« mos e realizojmĂ« kĂ«tĂ«? Le tĂ« kemi njĂ« varg asociativ, ku secilit çelĂ«s â njĂ« palĂ« e renditur numrash tĂ« tĂ«rĂ« â i korrespondon njĂ« vlerĂ« â njĂ« numĂ«r i plotĂ« ose i vĂ«rtetĂ«, qĂ« tregon peshĂ«n e brinjĂ«s. NĂ« C++, kjo strukturĂ« Ă«shtĂ« e arsyeshme tĂ« implementohet mbi bazĂ«n e kontenerit std::map (std::map<std::pair, int> ose std::map<std::pair, double>), ose std::multimap, nĂ«se parashikohen brinjĂ« tĂ« shumta. Dhe kĂ«shtu, kemi krijuar njĂ« strukturĂ« pĂ«r ruajtjen e grafĂ«ve, e cila pĂ«rdor mĂ« pak memorie se strukturat 'matrice', mund tĂ« pĂ«rshkruajĂ« grafĂ« me qarkullime dhe brinjĂ« tĂ« shumta dhe madje nuk ka kĂ«rkesa rigoroze pĂ«r numrat e pikat (nuk e di pĂ«r kĂ« Ă«shtĂ« kjo, por gjithsesi).
4. Strukturat e të dhënave ndonjëherë "derdh" dhe ndonjëherë mungon diçka
E vërtetë: kur zgjidhim disa probleme, mund të lindë nevoja për t'u dhënë brinjëve të grafit disa karakteristika dhe, për rrjedhojë, për t'i ruajtur ato. Nëse është e mundur të zvoglohen këto karakteristika në numra të tërë, atëherë është e mundur të ruhet një "graf me karakteristika të shtesë" duke përdorur versione të zgjeruara të vektorit të ngjashmërisë dhe të array të asociohueshëm.
Pra ndaj, le tĂ« supozojmĂ« se kemi njĂ« grafik tĂ« peshkuar, pĂ«r çdo buzĂ« tĂ« tĂ« cilit ne na nevojiten, pĂ«r shembull, 2 karakteristika shtesĂ«, tĂ« pĂ«rcaktuara nga numra tĂ« plotĂ«. NĂ« kĂ«tĂ« rast, mund ta pĂ«rcaktojmĂ« vektorin e tij tĂ« fqinjĂ«sisĂ« si njĂ« grup tĂ« renditur jo "çifte", por "grupe" tĂ« katĂ«r numrash tĂ« plotĂ« (a[2i], a[2i+1], a[2i+2], a[2i+3]âŠ), ku a[2i+2] dhe a[2i+3] do tĂ« pĂ«rcaktojnĂ« karakteristikat pĂ«rkatĂ«se tĂ« buzĂ«s. PĂ«r grafikĂ«t me pesha tĂ« plotĂ« tĂ« buzĂ«ve, rregulli nĂ« pĂ«rgjithĂ«si Ă«shtĂ« i ngjashĂ«m (ndryshimi do tĂ« jetĂ« vetĂ«m se karakteristikat do tĂ« vijnĂ« pas peshĂ«s sĂ« buzĂ«s dhe do tĂ« pĂ«rcaktohen nga elementĂ«t a[2i+3] dhe a[2i+4], ndĂ«rsa vetĂ« buza do tĂ« pĂ«rcaktohet nga 5 numra tĂ« renditur). PĂ«r grafikĂ«t me pesha jo tĂ« plota tĂ« buzĂ«ve, karakteristikat mund tĂ« shkruhen nĂ« komponentin e tij pa peshĂ«.
Duke përdorimi i një array asociativ të ngjashmërisë për grafët me pesha të plotë, është e mundur të caktohet si vlerë jo vetëm një numër i veçantë, por një array (vektor) numrash që përcaktojnë, përveç peshe së skelës, të gjithë karakteristikat e tij të tjera të nevojshme. Në këtë rast, një shqetësim për rastin e peshave jo të plota do të jetë nevoja për të caktuar një karakteristikë si një numër me pikë fluturuese (po, ky është një shqetësim, por nëse nuk ka shumë karakteristika të tilla dhe nëse nuk i caktohen shumë "të sofistikuara" double, atëherë ndoshta do të ishte mirë). Kështu, në C++, array-t e zgjeruara asociative të ngjashmërisë mund të caktohen në mënyrën e mëposhtme: std::map <std::pair , std::vector > ose std::map <std::pair , std::vector>, ku vlera e parë në "vektorin-vlerë-për-çelësin" do të jetë peshë e skelës, dhe më pas ndodhen numrat që i përfaqësojnë karakteristikat e tij.
Literatura:
Për grafët dhe algoritmet në përgjithësi:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmet: ndërtimi dhe analiza, edicioni i dytë: Përkthim nga anglishtja - M.: Shtëpia Botuese "Williams", 2011.
2. Harari Frank. Teoria e grafëve. M.: Botime Bota, 1973.
Raporti i autorit për këto vektor dhe hartën asociative të fqinjësisë:
3. Chernohou S.A. Vektori i fqinjĂ«sisĂ« dhe harta asociative si mĂ«nyra pĂ«r tĂ« pĂ«rfaqĂ«suar dhe ruajtur grafet / S.A. Chernohou. Vektori i fqinjĂ«sisĂ« dhe harta e fqinjĂ«sisĂ« si struktura tĂ« dhĂ«nash pĂ«r tĂ« pĂ«rfaqĂ«suar njĂ« graf / / Mbledhja e artikujve tĂ« KonferencĂ«s NdĂ«rkombĂ«tare Shkencore dhe Praktike "Problemet e zbatimit tĂ« rezultateve tĂ« zhvillimeve inovative dhe mĂ«nyrat pĂ«r zgjidhjen e tyre" (Saratov, 14.09.2019). â Sterlitamak: AMI, 2019, fq. 65-69
Burimet e dobishme në internet për temën:
4.
5.
Burimi: habr.com
