Pershendetje te gjitheve
Në këtë shënim, vendosa të rendis strukturat kryesore të të dhënave të përdorura për ruajtjen e grafikëve në shkencën kompjuterike, dhe gjithashtu do të flas për disa struktura të tjera të tilla që disi "kristalizuan" për mua.
Pra, le të fillojmë. Por jo që në fillim - mendoj se të gjithë e dimë tashmë se çfarë është një grafik dhe çfarë janë ata (i drejtuar, i padrejtuar, i peshuar, i papeshuar, me ose pa skaje dhe sythe të shumta).
Pra, le të shkojmë. Çfarë opsionesh për strukturat e të dhënave për "ruajtjen e grafikëve" kemi?
1. Strukturat e të dhënave të matricës
1.1 Matrica e fqinjësisë. Matrica e fqinjësisë është një matricë ku titujt e rreshtave dhe kolonave korrespondojnë me numrat e kulmeve të grafikut, dhe vlera e secilit prej elementeve të saj a(i,j) përcaktohet nga prania ose mungesa e skajeve midis kulmeve. i dhe j (është e qartë se për një grafik të padrejtuar, një matricë e tillë do të jetë simetrike, ose mund të pajtohemi që të gjitha vlerat t'i ruajmë vetëm mbi diagonalen kryesore). Për grafikët e papeshuar, a(i,j) mund të vendoset nga numri i skajeve nga i në j (nëse nuk ka një skaj të tillë, atëherë a(i,j)= 0), dhe për grafikët e ponderuar, gjithashtu nga pesha (pesha totale) e skajeve të përmendura.
1.2 Matrica e incidencës. Në këtë rast, grafiku ynë ruhet gjithashtu në një tabelë në të cilën, si rregull, numrat e rreshtave korrespondojnë me numrat e kulmeve të tij, dhe numrat e kolonave korrespondojnë me skajet e para-numëruara. Nëse një kulm dhe një skaj janë incidente me njëri-tjetrin, atëherë një vlerë jo zero shkruhet në qelizën përkatëse (për grafët e padrejtuar, 1 shkruhet nëse kulmi dhe skaji janë incidente, për grafët e orientuar - "1" nëse buza "daljet" nga kulmi dhe "-1" nëse "përfshin" në të (është mjaft e lehtë për t'u mbajtur mend, sepse shenja "minus" gjithashtu duket se "përfshihet" në numrin "-1")). Për grafikët e peshuar, përsëri, në vend të 1 dhe -1, mund të specifikoni peshën totale të skajit.
2. Strukturat e të dhënave të numërimit
2.1 Lista e fqinjësisë. Epo, gjithçka duket të jetë e thjeshtë këtu. Çdo kulm i grafikut, në përgjithësi, mund të shoqërohet me çdo strukturë numërimi (listë, vektor, varg, ...), e cila do të ruajë numrat e të gjitha kulmeve ngjitur me atë të dhënë. Për grafikët e drejtuar, në një listë të tillë do t'i shtojmë vetëm ato kulme në të cilat ka një skaj "të drejtuar" nga një kulm tipar. Për grafikët e peshuar, zbatimi do të jetë më kompleks.
2.2 Lista e brinjëve. Një strukturë mjaft e njohur e të dhënave. Lista e skajeve, siç na thotë Kapiteni Obviousness, është në të vërtetë një listë e skajeve të grafikut, secila prej të cilave specifikohet nga kulmi fillestar, kulmi i mbarimit (për grafët e padrejtuar renditja nuk është e rëndësishme këtu, megjithëse për unifikimin mund të përdorni rregulla të ndryshme, për shembull, duke specifikuar kulmet sipas renditjes në rritje) dhe peshën (vetëm për grafikët e peshuar).
Ju mund t'i shikoni listat e matricës të listuara më sipër në më shumë detaje (dhe me ilustrime), për shembull, .
2.3 Vargu i afërsisë. Jo struktura më e zakonshme. Në thelb, ajo është një formë e "paketimit" të listave të afërsisë në një strukturë numërimi (vargu, vektor). Elementet e para n (sipas numrit të kulmeve të grafikut) të një vargu të tillë përmbajnë indekset fillestare të të njëjtit varg, duke filluar nga i cili shkruhen me radhë të gjitha kulmet ngjitur me atë të dhënë.
Këtu gjeta shpjegimin më të kuptueshëm (për veten time):
3. Vektori i afërsisë dhe vargu i afërsisë asociative
Doli se autori i këtyre rreshtave, duke mos qenë një programues profesionist, por që merrej periodikisht me grafikë, më së shpeshti merrej me lista të skajeve. Në të vërtetë, është i përshtatshëm nëse grafiku ka sythe dhe skaje të shumta. Dhe kështu, në zhvillimin e listave klasike të skajeve, unë propozoj t'i kushtohet vëmendje "zhvillimit / degës / modifikimit / mutacionit" të tyre, përkatësisht: vektorit të afërsisë dhe grupit të afërsisë shoqëruese.
3.1 Vektori i fqinjësisë
Rasti (a1): grafiku i papeshuar
Ne do të quajmë një vektor fqinjësie për një graf të papeshuar një grup të renditur të një numri çift numrash të plotë (a[2i], a[2i+1],..., ku i numërohet c 0), në të cilin çdo çift numrash është a[2i], a[2i+1] specifikon një skaj të grafikut ndërmjet kulmeve a[2i] dhe a[2i+1], respektivisht.
Ky format regjistrimi nuk përmban informacion nëse grafiku është i drejtuar (të dyja opsionet janë të mundshme). Kur përdorni formatin e digrafit, skaji konsiderohet të jetë i drejtuar nga a[2i] në a[2i+1]. Këtu dhe më poshtë: për grafikët e padrejtuar, nëse është e nevojshme, mund të aplikohen kërkesat për rendin e regjistrimit të kulmeve (për shembull, që maja me vlerën më të ulët të numrit të caktuar të vijë e para).
Në C++, këshillohet të specifikoni një vektor fqinjësie duke përdorur std::vector, pra emri i kësaj strukture të dhënash.
Rasti (a2): grafiku i papeshuar, peshat e skajeve janë numër i plotë
Në analogji me rastin (a1), ne e quajmë vektorin e afërsisë për një graf të ponderuar me pesha të skajeve të plotë një grup të renditur (varg dinamik) numrash (a[3i], a[3i+1], a[3i+2], ..., ku i numërohet c 0), ku çdo “treshe” e numrave a[3i], a[3i+1], a[3i+2] specifikon një skaj të grafikut midis kulmeve me numër a[3i] dhe a[3i+1], përkatësisht, dhe vlera a [3i+2] është pesha e kësaj skaji. Një grafik i tillë gjithashtu mund të jetë i drejtuar ose jo.
Rasti (b): grafiku i papeshuar, peshat e skajeve jo të plota
Meqenëse është e pamundur të ruhen elementë heterogjenë në një grup (vektor), për shembull, zbatimi i mëposhtëm është i mundur. Grafiku ruhet në një çift vektorësh, në të cilin vektori i parë është vektori i afërsisë së grafikut pa specifikuar peshat, dhe vektori i dytë përmban peshat përkatëse (zbatimi i mundshëm për C++: std:: çift ). Kështu, për një skaj të përcaktuar nga një palë kulme nën indekset 2i, 2i+1 të vektorit të parë, pesha do të jetë e barabartë me elementin nën indeksin i të vektorit të dytë.
Epo, pse është e nevojshme kjo?
Epo, autori i këtyre rreshtave e gjeti atë mjaft të dobishëm për zgjidhjen e një sërë problemesh. Epo, nga një këndvështrim formal, do të ketë përparësitë e mëposhtme:
- Vektori i afërsisë, si çdo strukturë tjetër "numerative", është mjaft kompakte, merr më pak memorie se matrica e afërsisë (për grafikë të rrallë) dhe është relativisht i lehtë për t'u zbatuar.
- Kulmet e grafikut, në parim, mund të shënohen edhe me numra negativë. Po sikur të nevojitet një “perversion” i tillë?
- Grafikët mund të përmbajnë skaje të shumta dhe sythe të shumta, me pesha të ndryshme (pozitive, negative, madje edhe zero). Këtu nuk ka kufizime.
- Ju gjithashtu mund të caktoni veti të ndryshme për skajet - por për më shumë rreth kësaj, shihni seksionin 4.
Sidoqoftë, duhet pranuar se kjo "listë" nuk nënkupton qasje të shpejtë në skaj. Dhe këtu Array Associative Adjacency vjen në shpëtim, e cila diskutohet më poshtë.
3.2 Vargu shoqërues fqinjësie
Pra, nëse qasja në një skaj të caktuar, pesha e tij dhe vetitë e tjera janë kritike për ne, dhe kërkesat e kujtesës nuk na lejojnë të përdorim matricën e afërsisë, atëherë le të mendojmë se si mund ta ndryshojmë vektorin e afërsisë për të zgjidhur këtë problem. Pra, çelësi është një skaj i grafikut, i cili mund të specifikohet si një çift i renditur i numrave të plotë. Si duket kjo? A nuk është një çelës në një grup shoqërues? Dhe, nëse po, pse nuk e zbatojmë atë? Le të kemi një grup shoqërues ku çdo çelës - një çift i renditur i numrave të plotë - do të shoqërohet me një vlerë - një numër të plotë ose një numër real që specifikon peshën e skajit. Në C++, këshillohet të zbatohet kjo strukturë bazuar në kontejnerin std::map (std::map , int> ose std::map , double>), ose std::multimap nëse priten skaje të shumta. Epo, ne kemi një strukturë për ruajtjen e grafikëve që merr më pak memorie sesa strukturat "matricë", mund të përcaktojë grafikë me sythe dhe skaje të shumta dhe nuk ka as kërkesa strikte për mosnegativitetin e numrave të kulmit (nuk e di kush ka nevojë për këtë, por gjithsesi).
4. Strukturat e të dhënave janë plot, por diçka mungon
Dhe është e vërtetë: kur zgjidhim një numër problemesh, mund të na duhet të caktojmë disa karakteristika në skajet e grafikut dhe, në përputhje me rrethanat, t'i ruajmë ato. Nëse është e mundur që këto veçori të reduktohen në mënyrë të paqartë në numra të plotë, atëherë është e mundur të ruhen "grafikë të tillë me veçori shtesë" duke përdorur versione të zgjeruara të vektorit të afërsisë dhe grupit të afërsisë shoqëruese.
Pra, le të kemi një grafik të papeshuar, për secilën skaj të të cilit është e nevojshme të ruhen, për shembull, 2 veçori shtesë të specifikuara nga numra të plotë. Në këtë rast, është e mundur të përkufizohet vektori i afërsisë së tij si një grup i renditur jo "çiftesh", por "katërshe" 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 e skajit përkatës. Për një grafik me peshë të plotë të skajeve, rendi është përgjithësisht i ngjashëm (i vetmi ndryshim do të jetë se atributet do të ndjekin peshën e skajit dhe do të specifikohen nga elementët a[2i+3] dhe a[2i+4] , dhe vetë buza do të specifikohet jo 4, por 5 numra të renditur). Dhe për një grafik me pesha të skajeve jo të plotë, veçoritë mund të shkruhen në përbërësin e tij të papeshuar.
Kur përdorni një grup afërsie shoqëruese për grafikë me pesha të skajeve me numër të plotë, është e mundur të specifikoni si vlerë jo një numër të vetëm, por një grup (vektor) numrash që specifikojnë, përveç peshës së një skaji, të gjitha të tjerat e nevojshme të tij. veçoritë. Në të njëjtën kohë, një shqetësim për rastin e peshave jo të plota do të jetë nevoja për të specifikuar një shenjë me një numër me pikë lundruese (po, kjo është një bezdi, por nëse nuk ka aq shumë shenja të tilla, dhe nëse nuk 'Vendosni ato shumë "të ndërlikuara" dyfish, atëherë mund të jetë asgjë). Kjo do të thotë që në C++ vargjet e zgjeruara të afërsisë shoqëruese mund të përkufizohen si më poshtë: std::map , std::vector> ose std:: hartë , std::vektor, në të cilin vlera e parë në "vektorin kyç-vlerë" do të jetë pesha e skajit, dhe më pas vendosen emërtimet numerike të karakteristikave të tij.
Literatura:
Rreth grafikëve dhe algoritmeve në përgjithësi:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmet: ndërtim dhe analizë, botimi i dytë: Trans. nga anglishtja - M.: Shtëpia Botuese Williams, 2.
2. Harari Frank. Teoria e grafikut. M.: Mir, 1973.
Raporti i autorit në lidhje me të njëjtin grup vektorial dhe shoqërues të fqinjësive:
3. Chernoukhov S.A. Vektori i afërsisë dhe grupi i afërsisë shoqëruese si mënyra për të përfaqësuar dhe ruajtur grafikët / SA Chernouhov. Vektori i afërsisë dhe harta e afërsisë si struktura të dhënash për të përfaqësuar një grafik // Koleksion artikujsh të Konferencës Ndërkombëtare Shkencore dhe Praktike "Problemet e zbatimit të rezultateve të zhvillimeve inovative dhe mënyrat për t'i zgjidhur ato" (Saratov, 14.09.2019 shtator 2019). – Sterlitamak: AMI, 65, f. 69-XNUMX
Burime të dobishme në internet për këtë temë:
4.
5.
Burimi: www.habr.com