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
