Hæ allir
Í þessari athugasemd ákvað ég að skrá helstu gagnaskipulag sem notað er til að geyma línurit í tölvunarfræði, og ég mun líka tala um nokkra slíka uppbyggingu sem einhvern veginn „kristallaðist“ fyrir mig.
Svo, við skulum byrja. En ekki alveg frá upphafi - ég held að við vitum öll nú þegar hvað línurit er og hvað það er (stýrt, óstýrt, vegið, óvigt, með eða án margra brúna og lykkja).
Svo, við skulum fara. Hvaða valkosti fyrir gagnaskipulag fyrir „grafgeymslu“ höfum við?
1. Fylkisgagnaskipulag
1.1 Aðliggjandi fylki. Aðliggjandi fylki er fylki þar sem línu- og dálkafyrirsagnir samsvara númerum hornpunkta línuritsins og gildi hvers hluta þess a(i,j) ræðst af tilvist eða fjarveru brúna á milli hornpunkta i og j (það er ljóst að fyrir óstýrt línurit verður slíkt fylki samhverft, eða við getum verið sammála um að við geymum öll gildi aðeins fyrir ofan aðal skálínuna). Fyrir óvigtuð línurit er hægt að stilla a(i,j) með fjölda brúna frá i til j (ef það er engin slík brún, þá er a(i,j)= 0), og fyrir vegin línurit, einnig með þyngdinni (heildarþyngd) nefndra brúna.
1.2 Tíðnifylki. Í þessu tilviki er grafið okkar einnig geymt í töflu þar sem að jafnaði samsvara línunúmerin númerum hornpunkta þess og dálknúmerin samsvara fyrirframnúmeruðum brúnum. Ef hornpunktur og brún falla inn á milli, þá er gildi sem er ekki núll skrifað í samsvarandi reit (fyrir óstýrð línurit er 1 skrifað ef hornpunkturinn og brúnin falla inn, fyrir línurit - "1" ef brúnin „hættir“ úr hornpunktinum og „-1“ ef það „inniheldur“ í því (það er nógu auðvelt að muna, því „mínus“ táknið virðist líka vera „innifalið“ í tölunni „-1“)). Fyrir vegin línurit, aftur, í stað 1 og -1, geturðu tilgreint heildarþyngd brúnarinnar.
2. Upptalningargagnauppbygging
2.1 Aðliggjandi listi. Jæja, allt virðist vera einfalt hér. Hver hornpunktur grafsins getur almennt tengst hvaða upptalningauppbyggingu sem er (lista, vektor, fylki, ...), sem geymir tölur allra hornpunkta sem liggja að þeim tiltekna. Fyrir bein línurit, munum við bæta við slíkan lista aðeins þeim hornpunktum sem það er „bein“ brún að frá hornpunkti eiginleika. Fyrir vegin línurit verður útfærslan flóknari.
2.2 Listi yfir rifbein. Nokkuð vinsælt gagnaskipulag. Listinn yfir brúnir, eins og Captain Obviousness segir okkur, er í raun listi yfir brúnir grafsins, sem hver um sig er tilgreindur af upphafspunktinum, endapunktinum (fyrir óstýrð línurit er röðin ekki mikilvæg hér, þó að fyrir sameiningu sé hægt að notaðu ýmsar reglur, til dæmis að tilgreina hornpunkta í röð vaxandi) og þyngd (aðeins fyrir vegin línurit).
Þú getur skoðað fylkislistana sem taldir eru upp hér að ofan nánar (og með myndskreytingum), til dæmis, .
2.3 Aðliggjandi fylki. Ekki algengasta uppbyggingin. Í kjarna þess er það tegund af "pökkun" aðliggjandi listum í eina upptalningarbyggingu (fylki, vektor). Fyrstu n (samkvæmt fjölda hornpunkta á línuritinu) þættir slíkrar fylkis innihalda upphafsvísitölur sömu fylkis, og byrjar á því að allir hornpunktar sem liggja að því tilgreindu eru skrifaðir í röð.
Hér fann ég skiljanlegustu (fyrir sjálfan mig) skýringu:
3. Adjacency Vector og Associative Adjacency Array
Það kom í ljós að höfundur þessara lína, sem var ekki faglegur forritari, heldur fékkst reglulega við línurit, fjallaði oftast um lista yfir brúnir. Reyndar er það þægilegt ef línuritið hefur margar lykkjur og brúnir. Og svo, við þróun klassískra lista yfir brúnir, legg ég til að gefa gaum að „þróun/grein/breytingu/stökkbreytingu“ þeirra, nefnilega: aðlægðarvigur og tengda aðlægðarfylki.
3.1 Adjacency vektor
Tilvik (a1): óvegið línurit
Við köllum aðliggjandi vektor fyrir óvegið graf raðað mengi sléttra heiltalna (a[2i], a[2i+1],..., þar sem i er númerað c 0), þar sem hvert talnapar er a[2i], a[2i+1 ] tilgreinir línuritsbrún milli hornpunktanna a[2i] og a[2i+1], í sömu röð.
Þetta upptökusnið inniheldur ekki upplýsingar um hvort línuritinu sé beint (báðir valkostir eru mögulegir). Þegar tvíritasniðið er notað telst brúnin vera beint frá a[2i] til a[2i+1]. Hér og að neðan: fyrir óstýrð línurit, ef nauðsyn krefur, er hægt að beita kröfum um röð skráningarpunkta (til dæmis að hornpunkturinn með lægra gildi tölunnar sem honum er úthlutað komi fyrst).
Í C++ er ráðlegt að tilgreina aðliggjandi vektor með því að nota std::vector, þaðan er nafnið á þessari gagnabyggingu.
Tilvik (a2): óvegið graf, brúnarþyngdir eru heiltölur
Á hliðstæðan hátt við fall (a1), köllum við aðlægðarvigur fyrir vegið línurit með heiltölubrúnarþyngd raðað mengi (breytilegt fylki) af tölum (a[3i], a[3i+1], a[3i+2], ..., þar sem i er númerað c 0), þar sem hver „þrífill“ af tölum a[3i], a[3i+1], a[3i+2] tilgreinir brún á línuritinu á milli hornpunkta sem eru númeraðir a[3i] og a[3i+1], í sömu röð, og gildið a [3i+2] er þyngd þessarar brúnar. Slíkt graf getur líka verið annað hvort beint eða ekki.
Tilvik (b): óvegið línurit, kantþyngd sem ekki er heiltölu
Þar sem það er ómögulegt að geyma ólíka þætti í einu fylki (vektor), til dæmis, er eftirfarandi útfærsla möguleg. Línuritið er geymt í vigrupari, þar sem fyrsti vigurinn er nálægðarvigur línuritsins án þess að tilgreina þyngdina, og seinni vigurinn inniheldur samsvarandi þyngd (möguleg útfærsla fyrir C++: std::pair ). Þannig, fyrir brún sem er skilgreind af pari af hornpunktum undir vísitölum 2i, 2i+1 á fyrsta vigri, verður þyngdin jöfn frumefninu undir vísi i í seinni vigri.
Jæja, hvers vegna er þetta nauðsynlegt?
Jæja, höfundi þessara lína fannst það mjög gagnlegt til að leysa fjölda vandamála. Jæja, frá formlegu sjónarhorni, þá verða eftirfarandi kostir:
- Aðliggjandi vektorinn, eins og hver önnur „upptalning“ uppbygging, er frekar þétt, tekur minna minni en aðliggjandi fylki (fyrir dreifð línurit) og er tiltölulega auðvelt í framkvæmd.
- Í grundvallaratriðum má einnig merkja hornpunkta línuritsins með neikvæðum tölum. Hvað ef þörf er á slíkri „röskun“?
- Línurit geta innihaldið margar brúnir og margar lykkjur, með mismunandi þyngd (jákvæð, neikvæð, jafnvel núll). Hér eru engar takmarkanir.
- Þú getur líka úthlutað mismunandi eiginleikum á brúnir - en fyrir meira um það, sjá kafla 4.
Hins vegar verður að viðurkenna að þessi „listi“ felur ekki í sér skjótan aðgang að brúninni. Og hér kemur Associative Adjacency Array til bjargar, sem fjallað er um hér að neðan.
3.2 Félagsaðliggjandi fylki
Þannig að ef aðgangur að tiltekinni brún, þyngd hennar og aðrir eiginleikar eru mikilvægir fyrir okkur og minniskröfur leyfa okkur ekki að nota aðliggjandi fylki, þá skulum við hugsa um hvernig við getum breytt aðliggjandi vektornum til að leysa þetta vandamál. Svo, lykillinn er brún á línuritinu, sem hægt er að tilgreina sem raðað par af heiltölum. Hvernig lítur þetta út? Er það ekki lykill í associative array? Og ef svo er, hvers vegna innleiðum við það ekki? Við skulum hafa sambandsfylki þar sem hver lykill - raðað par af heiltölum - verður tengd við gildi - heiltölu eða rauntölu sem tilgreinir þyngd brúnarinnar. Í C++ er ráðlegt að útfæra þessa uppbyggingu byggt á std::map gámnum (std::map , int> eða std::kort , double>), eða std::multimap ef búist er við mörgum brúnum. Jæja, við höfum uppbyggingu til að geyma línurit sem tekur minna minni en „matrix“ kerfi, getur skilgreint línurit með mörgum lykkjum og brúnum og gerir ekki einu sinni strangar kröfur um óneikvæðni hornpunktstalna (ég veit það ekki) hver þarf þetta, en samt).
4. Gagnauppbygging er full, en eitthvað vantar
Og það er satt: þegar við leysum fjölda vandamála gætum við þurft að úthluta nokkrum eiginleikum á brúnir línuritsins og geyma þau í samræmi við það. Ef það er hægt að minnka þessa eiginleika ótvírætt niður í heilar tölur, þá er hægt að geyma slík „graf með viðbótareiginleikum“ með því að nota útvíkkaðar útgáfur af aðliggjandi vektornum og tengdum aðliggjandi fylki.
Svo skulum við hafa óvegið línurit, fyrir hverja brún þess er nauðsynlegt að geyma, til dæmis, 2 viðbótareiginleika sem tilgreindar eru með heiltölum. Í þessu tilviki er hægt að skilgreina aðliggjandi vektor þess sem röðað mengi, ekki af „pörum“, heldur „kvartettum“ af heiltölum (a[2i], a[2i+1], a[2i+2], a [2i+3]…), þar sem a[2i+2] og a[2i+3] munu ákvarða eiginleika samsvarandi brúnar. Fyrir línurit með heiltöluþyngd brúna er röðin almennt svipuð (eini munurinn verður sá að eiginleikarnir fylgja þyngd brúnarinnar og verða tilgreindir með þáttunum a[2i+3] og a[2i+4] , og brúnin sjálf verður ekki tilgreind 4, heldur 5 raðnúmer). Og fyrir línurit með brúnþyngd sem ekki er heiltölu, er hægt að skrifa eiginleikana í óvigtaða hluta þess.
Þegar tengt aðliggjandi fylki er notað fyrir línurit með heiltölubrúnarþyngd er hægt að tilgreina sem gildi ekki eina tölu, heldur fylki (vektor) af tölum sem tilgreina, auk þyngdar brúnar, allar aðrar nauðsynlegar eiginleikar. Á sama tíma mun óþægindi þegar um er að ræða þyngd sem ekki eru heiltölu vera þörf á að tilgreina skilti með flottölu (já, þetta er óþægindi, en ef það eru ekki svo mörg slík merki og ef þú gerir það ekki ekki stilla þá of „erfiðinn“ tvöfalt, þá gæti það verið ekkert). Þetta þýðir að í C++ er hægt að skilgreina útbreidda tengda aðliggjandi fylki sem hér segir: std::map , std::vector> eða std::kort , std::vektor, þar sem fyrsta gildið í „key-value-vector“ verður þyngd brúnarinnar, og síðan eru tölulegar merkingar á eiginleikum hans staðsettar.
Bókmenntir:
Um línurit og reiknirit almennt:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Reiknirit: smíði og greining, 2. útgáfa: Þýð. úr ensku – M.: Williams Publishing House, 2011.
2. Harari Frank. Línuritafræði. M.: Mir, 1973.
Skýrsla höfundar um þessa sömu vektor og tengda fylki aðlægra efna:
3. Chernoukhov S.A. Adjacency vektor og associative adjacency array sem leiðir til að tákna og geyma línurit / SA Chernouhov. Adjacency vektor og adjacency map sem gagnastrúktúr til að tákna línurit // Safn greina frá International Scientific and Practical Conference „Vandamál við að innleiða niðurstöður nýstárlegrar þróunar og leiðir til að leysa þær“ (Saratov, 14.09.2019. september, 2019). – Sterlitamak: AMI, 65, bls. 69-XNUMX
Gagnlegar heimildir á netinu um efnið:
4.
5.
Heimild: www.habr.com