Përshëndetje të gjithëve.
Në këtë shënim kam vendosur të listoj strukturat kryesore të të dhënave që përdoren për ruajtjen e grafëve në informatikë, si dhe do të flas për disa struktura të tjera që veçse më janë "krystallizuar".
Pra, le tĂ« fillojmĂ«. Por jo nga fillimi â mendoj se çfarĂ« Ă«shtĂ« njĂ« grafik dhe cilat janĂ« llojet e tij (tĂ« orientuara, tĂ« paorientuara, tĂ« peshuara, tĂ« papeshuara, me nyje tĂ« shumta dhe cikle ose pa to), tĂ« gjithĂ« tashmĂ« e dimĂ«.
Pra, le të shkojmë. Cilat janë opsionet për strukturat e të dhënave për "ruajtjen e grafëve" që kemi.
1. Strukturat e të dhënave matricore
1.1 MatricĂ« ngjashmĂ«rie. MatricĂ« ngjashmĂ«rie pĂ«rfaqĂ«son njĂ« matricĂ«, ku titujt e rreshtave dhe kolonave korrespondent me numrat e nyjeve tĂ« grafit, dhe vetĂ« vlera e çdo elementi tĂ« saj a(i,j) pĂ«rcaktohet nga prania ose mungesa e nyjeve mes nyjeve i dhe j (qartĂ«, pĂ«r grafĂ«t e paorientuar, kjo matricĂ« do tĂ« jetĂ« simetrike, ose mund tĂ« bien dakord qĂ« tĂ« gjithĂ« vlerat t'i ruajmĂ« vetĂ«m mbi diagonalen kryesore). PĂ«r grafĂ«t e pa peshuar a(i,j) mund tĂ« pĂ«rcaktohet si numri i nyjeve nga i nĂ« j (nĂ«se nuk ka njĂ« nyje tĂ« tillĂ«, atĂ«herĂ« a(i,j)= 0), dhe pĂ«r grafĂ«t e peshuar gjithashtu â si pesha (pesha totale) e nyjeve tĂ« pĂ«rmendura.
1.2 MatricĂ« incidenti. NĂ« kĂ«tĂ« rast, grafi ynĂ« gjithashtu ruhet nĂ« njĂ« tabelĂ«, ku, zakonisht, numrat e rreshtave pĂ«rkojnĂ« me numrat e nyjeve tĂ« tij, ndĂ«rsa numrat e kolonave â me nyjet e numĂ«ruara paraprakisht. NĂ«se njĂ« nyje dhe njĂ« nyje janĂ« incident tĂ« njĂ«ri-tjetrit, atĂ«herĂ« nĂ« qeliza pĂ«rkatĂ«s ekziston njĂ« vlerĂ« jo zero (pĂ«r grafĂ«t e paorientuar inspektohet 1 nĂ« rastin e incidentit midis nyjes dhe nyjes, pĂ«r grafĂ«t e orientuar â "1", nĂ«se nyja "duhet nga" nyja dhe "-1", nĂ«se ajo "shkon" nĂ« tĂ« (e kujtuar Ă«shtĂ« mjaft e lehtĂ«, sepse shenja "minus" gjithashtu "shkon" nĂ« numrin "-1"). PĂ«r grafĂ«t e peshuar gjithashtu, nĂ« vend tĂ« 1 dhe -1 mund tĂ« tregoni peshĂ«n totale tĂ« nyjes.
2. Strukturat e të dhënave enumeruese
2.1 Lista e ngjashmĂ«risĂ«. KĂ«tu duket se Ă«shtĂ« e thjeshtĂ«. Ădo kulm i grafit mund t'i korrespondon nĂ« pĂ«rgjithĂ«si njĂ« strukture enumerative (listĂ«, vektor, masiv, ...), ku do tĂ« ruhen numrat e tĂ« gjitha kulmeve tĂ« afĂ«rta. PĂ«r grafet e orientuara, nĂ« kĂ«tĂ« listĂ« do tĂ« pĂ«rfshijmĂ« vetĂ«m ato kulme nĂ« tĂ« cilat ekziston njĂ« skelĂ« e "orientuar" nga kulmi-nĂ«nshkrim. PĂ«r grafet e peshuara, realizimi do tĂ« jetĂ« mĂ« i komplikuar.
2.2 Listë skelesh. Një strukturë të dhënash mjaft popullore. Lista e skelesh, siç na sugjeron Kapiteni e Dukshme, përfaqëson pikërisht listën e skelesh të grafit, secila prej të cilave përcaktohet nga kulmi fillestar, kulmi përfundimtar (për grafet e paorientuara rendi i ndjekjes nuk ka rëndësi, megjithatë për unifikim mund të përdoren rregulla të ndryshme, për shembull, të përcaktohen kulmet në rendin në rritje) dhe pesha (vetëm për grafet e peshuara).
Mund të shihni më në detaje për listat-matricë të përmendura më sipër (dhe me ilustrime), për shembull, .
2.3 Masi i afërsisë. Nuk është një strukturë e zakonshme. Në thelb, ajo përfaqëson një formë "paketimi" të listave të afërsisë në një strukturë enumerative (masiv, vektor). Elementet e para n (sipër numrit të kulmeve të grafit) të këtij masivi përmbajnë indekset fillestare të këtij masivi, duke filluar nga e cila janë renditur të gjitha kulmet që janë afër kësaj.
Këtu kam gjetur shpjegimin më të qartë (për veten):
3. Vektori i afërsisë dhe Masi asociativ i afërsisë
Ka ndodhur që autori i këtyre rreshtave, ndërsa nuk është një programues profesional, megjithatë ka pasur përherë të bëjë me grafet, zakonisht ka punuar me listat e skelesh. Në të vërtetë, është e përshtatshme nëse në graf ka loops të shumta dhe skela. Dhe ndërlidhur me zhvillimin e klasikeve të listave të skelesh, sugjeroj t'i kushtohet vëmendje "zhvillimit / shpërndarjes / modifikimit / mutacionit" të tyre, pra: vektorit të afërsisë dhe masës asociative të afërsisë.
3.1 Vektori i afërsisë
Rasti (a1): graf i pa peshuar
Do ta quajmë vektor të afërsisë për një graf të pa peshuar një grup të renditur të numrave të tërë (a[2i], a[2i+1],⊠ku i numërohet nga 0), në të cilin secila çift numrash a[2i], a[2i+1] përcakton një skelë grafike mes kulmeve a[2i] dhe a[2i+1] përkatësisht.
Ky format regjistrimi nuk përmban informacion nëse grafiku është i orientuar (mund të jenë të dyja opsionet). Kur përdoret formati për graf, merret parasysh se një skaj është i orientuar nga a[2i] në a[2i+1]. Këtu dhe më tutje: për grafet jo-orientuar, në raste të nevojshme, mund të aplikohen kërkesat për rendin e regjistrimit të kulmave (p.sh., që të parën të jetë kulmi me numrin më të vogël të caktuar).
Në C++, është e arsyeshme të përcaktohet vektori i fqinjësisë me std::vector, ndaj u zgjodh ky emër për këtë strukturë të dhënash.
Rast (a2): grafi i pa peshuar, pesha e skajeve është e gjithë numër.
Me analogji me rastin (a1), do ta quajmĂ« vektor tĂ« fqinjĂ«sisĂ« pĂ«r grafin e peshuar me pesha tĂ« skajeve tĂ« gjithĂ« numĂ«r njĂ« set tĂ« renditur (nĂ« varg dinamik) numrash (a[3i], a[3i+1], a[3i+2],âŠ, ku i numĂ«rohet nga 0), ku çdo âtripletâ numrash a[3i], a[3i+1], a[3i+2] pĂ«rcakton njĂ« skaj grafi midis kulmave me numra 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.
Rast (b): grafi i pa peshuar, pesha e skajeve nuk është e gjithë numër.
Duke pasur parasysh se në një masiv (vektor) nuk mund të ruhen elemente të ndryshme, mund të ketë, për shembull, këtë zbatim. Grafi ruhet në një çift vektorësh, ku vektori i parë është vektori i fqinjësisë së grafit pa treguar peshat, ndërsa vektori i dytë përmban peshat përkatëse (një zbatim i mundshëm për C++: std::pair). Pra, për një skaj, i përcaktuar nga një çift kulmash nën indekset 2i, 2i+1 të vektorit të parë, pesha do të jetë e barabartë me elementin nën indeksi i të dytit.
Po, përse është kjo e nevojshme?
Autori i këtyre rreshtave e gjeti këtë mjaft të dobishëm për zgjidhjen e disa problemeve. Nga një pikëpamje formale, këtu do të jenë disa përfitime:
- Vektori i fqinjĂ«sisĂ«, ashtu si çdo strukturĂ« tjetĂ«r âenumerativeâ, Ă«shtĂ« mjaft kompakt, zĂ« mĂ« pak memorie se matrica e fqinjĂ«sisĂ« (pĂ«r grafĂ«t e hollĂ«), dhe Ă«shtĂ« relativisht e lehtĂ« pĂ«r tu implementuar.
- Kulmat e grafit, nĂ« parim, mund tĂ« etiketohen me numra dhe negative. Mund tĂ« ndodhĂ« qĂ« tĂ« nevojitet dhe njĂ« âçmenduriâ e tillĂ«.
- Grafet mund të përmbajnë skaje të shumta dhe cikle të shumta, me pesha të ndryshme (pozitive, negative, madje edhe zero). Nuk ka asnjë kufizim këtu.
- Gjithashtu, kĂ«ndvĂ«shtrave mund t'u jepen prona tĂ« ndryshme â por pĂ«r kĂ«tĂ« shihni p. 4.
MegjithatĂ«, duhet pranuar se qasja e shpejtĂ« nĂ« kĂ«ndvĂ«shtrimin e kĂ«tij "listimi" nuk parashikohet. Dhe kĂ«tu ndihmon Asociativni array i afĂ«rsive, pĂ«r tĂ« cilin â mĂ« poshtĂ«.
3.2 Asociativni array i afërsive
Pra, nĂ«se pĂ«r ne qasja nĂ« njĂ« kĂ«ndvĂ«shtrim tĂ« caktuar, pesha e tij dhe prona tĂ« tjera janĂ« kritike, dhe kĂ«rkesat pĂ«r memorie nuk lejojnĂ« pĂ«rdorimin e matricĂ«s sĂ« afĂ«rsive, le tĂ« mendojmĂ« se si mund tĂ« ndryshojmĂ« vektorĂ«t e afĂ«rsive pĂ«r tĂ« zgjidhur kĂ«tĂ« problem. Pra, çelĂ«si Ă«shtĂ« kĂ«ndvĂ«shtrimi i grafikut, i cili mund tĂ« definihet si njĂ« çift i renditur i numrave tĂ« plotĂ«. ĂfarĂ« ngjan me kĂ«tĂ«? A nuk Ă«shtĂ« ky njĂ« çelĂ«s nĂ« asociativin array? Dhe, nĂ«se Ă«shtĂ« kĂ«shtu, pse tĂ« mos e implementojmĂ« kĂ«tĂ«? Le tĂ« kemi njĂ« asociativ array, ku çdo çelĂ«s â çift i renditur i numrave tĂ« plotĂ« â do tĂ« lidhet me njĂ« vlerĂ« â numĂ«r tĂ« plotĂ« ose real, qĂ« pĂ«rcakton peshĂ«n e kĂ«ndvĂ«shtrimit. NĂ« C++ Ă«shtĂ« e arsyeshme tĂ« implementohet kjo strukturĂ« mbi bazĂ«n e kontejnerit std::map (std::map <std::pair , int> ose std::map <std::pair , double>), ose std::multimap, nĂ«se parashikohen kĂ«ndvĂ«shtrime tĂ« shumta. Dhe ja, kemi krijuar njĂ« strukturĂ« pĂ«r ruajtjen e grafikĂ«ve, e cila zĂ« mĂ« pak memorie se strukturat "matrike", mund tĂ« pĂ«rcaktojĂ« grafikĂ« me cikle tĂ« shumta dhe kĂ«ndvĂ«shtrime dhe madje nuk ka kĂ«rkesa tĂ« ngurta pĂ«r numrat e pachesive (nuk di se kujt i nevojitet kjo, por gjithsesi).
4. Strukturat e të dhënave, sa më shumë të shtoni, diçka mungon
Dhe e vërteta është: kur zgjidhim disa probleme, mund të kemi nevojë të atribuojmë disa karakteristika këndvështrimeve të grafit dhe, për pasojë, t'i ruajmë ato. Nëse është e mundur të reduktohen njësh më njësh këto karakteristika në numra të plotë, atëherë është e mundur të ruajmë të tillë "grafikë me karakteristika shtesë" duke përdorur versionet e zgjeruara të vektorëve të afërsisë dhe asociativëve të afërsive.
Tani, le tĂ« kemi njĂ« graf tĂ« papĂ«rgatitur, pĂ«r çdo skaj tĂ« tĂ« cilit duhet tĂ« ruajmĂ«, pĂ«r shembull, 2 karakteristika shtesĂ« tĂ« caktuara me numra tĂ« plotĂ«. NĂ« kĂ«tĂ« rast, mund ta caktosh vektorin e tij tĂ« fqinjĂ«sisĂ« si njĂ« grup tĂ« renditur jo si "çifte", por si "katĂ«r" numra 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 e skajit pĂ«rkatĂ«s. PĂ«r grafikun me peshat e plota tĂ« skajeve, rendi, nĂ« pĂ«rgjithĂ«si, Ă«shtĂ« i ngjashĂ«m (ndryshimi do tĂ« jetĂ« vetĂ«m se karakteristikat do tĂ« vijnĂ« pas peshĂ«s sĂ« skajit dhe do tĂ« caktohen nga elementet a[2i + 3] dhe a[2i + 4], dhe skaji do tĂ« caktohet jo me 4 numra tĂ« renditur, por me 5). NdĂ«rsa pĂ«r grafin me peshat jo tĂ« plota, karakteristikat do tĂ« mund tĂ« regjistrohen nĂ« komponentĂ«n e tij tĂ« papĂ«rgatitur.
Kur përdoret një masë asociative fqinjësie për grafet me peshat e plota të skajeve, është e mundur të caktohet si vlerë jo një numër i vetëm, por një masiv (vektor) numrash, që përcakton, përveç peshës së skajit, të gjitha karakteristikat e tjera të nevojshme. Megjithatë, një pengesë për rastin e peshave jo të plota do të jetë nevoja për të caktuar karakteristikën si një numër me notacion të lëvizshëm (po, kjo është një pengesë, por nëse nuk ka shumë të tilla dhe nëse ato nuk janë shumë "të zgjuara" double, ndoshta është gjithçka në rregull). Pra, në C++, masat e zgjeruara asociative të fqinjësisë mund të caktohen si: std::map <std::pair , std::vector> ose std::map <std::pair , std::vector, duke pasur parasysh se vlera e parë në "vektorin-vlerë-për-çelës" do të jetë pesha e skajit, dhe më tutje do të përmbajnë shenjat numerike të karakteristikave të tij.
Literatura:
Për grafet dhe algoritmet në përgjithësi:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmet: ndĂ«rtimi dhe analiza, botimi i dytĂ«: PĂ«rkthim nga anglishtja â MoskĂ«: ShtĂ«pia Botuese 'Williams', 2011.
2. Harari Frank. Teoria e grafëve. Moskë: Botimi, 1973.
Raporti i autorit për këto sama vektor dhe masë asociative fqinjësie:
3. Chernoukhova S.A. Vektori i grupe afĂ«rsie si mĂ«nyra pĂ«rfaqĂ«simi dhe ruajtjeje e grafeve / S.A. Chernouhov. Vektori i afĂ«rsisĂ« dhe harta e afĂ«rsisĂ« si struktura tĂ« dhĂ«nash pĂ«r tĂ« pĂ«rfaqĂ«suar njĂ« graf // Grumbullimi i artikujve tĂ« KonferencĂ«s NdĂ«rkombĂ«tare Shkencore-Praktike "Problemet e zbatimit tĂ« rezultateve tĂ« zhvillimeve inovative dhe rrugĂ«t pĂ«r zgjidhjen e tyre" (Saratov, 14.09.2019). â Sterlitamak: AMI, 2019, fq. 65-69
Burimet e dobishme në internet mbi temën:
4.
5.
Burimi: habr.com
