Kaixo guztioi
Ohar honetan, informatikan grafikoak gordetzeko erabiltzen diren datu-egitura nagusiak zerrendatzea erabaki dut, eta nolabait "kristalizatu" zaizkidan egitura pare bat gehiagoz ere hitz egingo dut.
Beraz, has gaitezen. Baina ez hasiera-hasieratik - uste dut denok dakigula jada zer den grafiko bat eta zer diren (zuzendua, zuzendua, haztatua, haztatu gabea, ertz eta begizta anitzekin edo gabe).
Beraz, goazen. Zer aukera ditugu "grafiko biltegiratzeko" datu egituretarako?
1. Matrizearen datu-egiturak
1.1 Aldakortasun matrizea. Aldaztasun-matrizea matrize bat da, non errenkada eta zutabeen goiburuak grafikoaren erpinen zenbakiekin bat datozen eta bere elementu bakoitzaren balioa a(i,j) erpinen arteko ertzak egoteak edo ezak zehazten du. i eta j (argi dago zuzendu gabeko grafiko baterako matrize hori simetrikoa izango dela, edo ados egon gaitezke balio guztiak diagonal nagusiaren gainetik soilik gordetzen ditugula). Grafiko haztatu gabekoetarako, a(i,j) i-tik j-rako ertz kopuruaren arabera ezar daiteke (ertz hori ez badago, orduan a(i,j)= 0), eta grafiko haztatuetarako, pisuaren arabera ere. (pisu osoa) aipatutako ertzen.
1.2 Intzidentzia matrizea. Kasu honetan, gure grafikoa ere taula batean gordetzen da, non, normalean, errenkada-zenbakiak bere erpinen zenbakiei dagozkie eta zutabe-zenbakiak aurrez zenbakitutako ertzei dagozkie. Erpin bat eta ertz bat elkarren artean intzidenteak badira, balio ez nulua dagokio gelaxkan idazten da (zuzendu gabeko grafikoetarako, 1 idazten da erpina eta ertza intzidenteak badira, grafiko orientatuetarako - "1" ertza bada. “irteera” erpinetik eta “-1” bertan “barne” badu (aski erraza da gogoratzea, “minus” ikurra ere “-1” zenbakian “sartuta” dagoela dirudielako). Grafiko haztatuetarako, berriro ere, 1 eta -1 beharrean, ertzaren pisu osoa zehaztu dezakezu.
2. Zenbaketa-datuen egiturak
2.1 Albokotasun zerrenda. Beno, badirudi hemen dena erraza dela. Grafikoaren erpin bakoitza, oro har, edozein enumerazio-egiturarekin (zerrenda, bektore, array,...) lotu daiteke, eta horrek emandakoaren ondoan dauden erpin guztien zenbakiak gordeko ditu. Grafiko zuzenduetarako, zerrenda horri ezaugarri erpin batetik ertz "zuzendua" duten erpinak bakarrik gehituko ditugu. Grafiko haztatuetarako ezarpena konplexuagoa izango da.
2.2 Saihetsen zerrenda. Datu-egitura nahiko ezaguna. Ertz-zerrenda, Captain Obviousness-ek esaten digunez, benetan grafikoaren ertzen zerrenda bat da, eta horietako bakoitza hasierako erpinaren bidez zehazten da, amaierako erpinarekin (zuzendu gabeko grafikoetarako ordena ez da garrantzitsua hemen, nahiz eta bateratzeko aukera izan dezakezu). erabili hainbat arau, adibidez, erpinak handituz ordenan zehaztuz) eta pisua (grafo haztatuetarako soilik).
Goian zerrendatutako matrize zerrendak zehatzago (eta ilustrazioekin) ikus ditzakezu, adibidez, .
2.3 Aldakortasun-matrizea. Ez da ohikoena egitura. Oinarrian, aldakortasun-zerrendak enumerazio-egitura bakarrean (matrizea, bektorea) "paketatzeko" modu bat da. Array horren lehen n (grafikoaren erpin kopuruaren arabera) elementuek matrize beraren hasierako indizeak dituzte, eta bertatik emandakoaren ondoan dauden erpin guztiak errenkadan idazten dira.
Hemen aurkitu dut (niretzat) azalpen ulergarriena:
3. Aldakortasun-bektorea eta elkartasun-matrizea
Lerro hauen egileak, programatzaile profesionala ez izaki, aldizka grafikoak jorratzen zituena, gehienetan ertz zerrendak jorratzen zituela. Izan ere, komenigarria da grafikoak begizta eta ertz anitz baditu. Beraz, ertz-zerrenda klasikoen garapenean, haien “garapena/adar/aldaketa/mutazioari” erreparatzea proposatzen dut, hots: ondokotasun-bektorea eta elkartze-matrizea.
3.1 Aldakortasun-bektorea
Kasua (a1): grafiko ponderatu gabea
Grafiko haztatu gabeko baten ondokotasun-bektore bati zenbaki oso bikoiti baten multzo ordenatua deituko diogu (a[2i], a[2i+1],..., non i c 0 den), zeinetan zenbaki pare bakoitza. a[2i] da, a[2i+1 ] a[2i] eta a[2i+1] erpinen arteko ertz grafikoa zehazten du, hurrenez hurren.
Grabaketa formatu honek ez du grafikoa zuzenduta dagoen ala ez adierazten duen informaziorik (aukera biak posible dira). Digrafo formatua erabiltzean, ertza a[2i]-tik a[2i+1-era zuzenduta dagoela jotzen da. Hemen eta behean: zuzendu gabeko grafikoetarako, beharrezkoa bada, erpinak erregistratzeko ordenaren eskakizunak aplika daitezke (adibidez, esleitutako zenbakiaren balio baxuena duen erpina lehena izatea).
C++-n, komeni da std::vector erabiliz ondokotasun-bektore bat zehaztea, hortik dator datu-egitura honen izena.
Kasua (a2): haztatu gabeko grafikoa, ertz pisuak osoak dira
(a1) kasuaren analogiaz, ertz osoko pisuak dituen grafiko haztatu baten ondokotasun-bektoreari zenbakien multzo ordenatua (matrize dinamikoa) deitzen diogu (a[3i], a[3i+1], a[3i+2], ..., non i zenbakitua c 0 den), non a[3i], a[3i+1], a[3i+2] zenbakien “hirukote” bakoitzak a[3i] zenbakidun erpinen arteko grafikoaren ertz bat zehazten du. eta a[3i+1], hurrenez hurren, eta a [3i+2] balioa ertz horren pisua da. Halako grafiko bat ere zuzendua izan daiteke edo ez.
(b) kasua: haztatu gabeko grafikoa, osorik gabeko ertz pisuak
Elementu heterogeneoak array batean (bektore) gordetzea ezinezkoa denez, adibidez, honako inplementazioa posible da. Grafikoa bektore pare batean gordetzen da, zeinetan lehenengo bektorea grafikoaren aldameneko bektorea da pisuak zehaztu gabe, eta bigarren bektoreak dagozkion pisuak ditu (C++-rako inplementazio posiblea: std::pair ). Horrela, lehen bektorearen 2i, 2i+1 indizeen azpian erpin pare batek definitutako ertz baterako, pisua bigarren bektorearen i indizearen azpian dagoen elementuaren berdina izango da.
Beno, zergatik da hau beharrezkoa?
Bada, lerro hauen egileari nahiko baliagarria iruditu zaio hainbat arazo konpontzeko. Bada, ikuspegi formaletik, abantaila hauek izango dira:
- Aldaztasun-bektorea, beste edozein egitura "zenbatatibo" bezala, nahiko trinkoa da, aldameneko matrizeak baino memoria gutxiago hartzen du (grafiko eskasetarako) eta nahiko erraza da inplementatzen.
- Grafikoaren erpinak, printzipioz, zenbaki negatiboekin ere marka daitezke. Zer gertatzen da halako “perbertsioa” behar bada?
- Grafikoek hainbat ertz eta begizta anitz izan ditzakete, pisu ezberdinekin (positibo, negatibo, nahiz zero). Hemen ez dago murrizketarik.
- Ertzei ere propietate desberdinak esleitu diezaiekezu, baina horri buruzko informazio gehiagorako, ikus 4. atala.
Hala ere, onartu beharra dago "zerrenda" horrek ez duela esan nahi ertzera azkar sartzea. Eta hemen Associative Adjacency Array erreskatatzera dator, behean eztabaidatzen dena.
3.2 Aldakortasun-matrize asoziatiboa
Beraz, ertz zehatz baterako sarbidea, bere pisua eta beste propietate batzuk funtsezkoak badira guretzat, eta memoria-eskakizunek ez badigute ondokotasun-matrizea erabiltzen uzten, orduan pentsa dezagun nola alda dezakegun aldatzentzia-bektorea arazo hau konpontzeko. Beraz, gakoa grafikoaren ertz bat da, zenbaki osoen pare ordenatu gisa zehaztu daitekeena. Zer itxura du honek? Ez al da gako bat array elkartu batean? Eta, hala bada, zergatik ez dugu ezartzen? Har dezagun matrize elkartu bat non gako bakoitza - zenbaki osoen pare ordenatu bat - balio batekin lotuko den - ertzaren pisua zehazten duen zenbaki oso edo erreal batekin. C++-n, komeni da egitura hau std::map edukiontzian oinarrituta ezartzea (std::map , int> edo std::map , double>), edo std::multiap ertz anitz espero badira. Bada, grafikoak gordetzeko egitura dugu, “matrize” egiturek baino memoria gutxiago hartzen duena, begizta eta ertz anitz dituzten grafikoak defini ditzakeena eta erpin-zenbakien ez-negatibotasunerako baldintza zorrotzik ere ez daukana (ez dakit nork behar du hau, baina hala ere).
4. Datu-egiturak beteta daude, baina zerbait falta da
Eta egia da: hainbat problema ebazteko orduan, baliteke grafikoaren ertzei ezaugarri batzuk esleitu eta, horren arabera, gorde behar izatea. Ezaugarri horiek zenbaki osoetara murriztea posible bada, orduan posible da "ezaugarri gehigarriekin grafikoak" gordetzea aldameneko bektorearen eta elkartze-matrizearen bertsio hedatuak erabiliz.
Beraz, har dezagun haztatu gabeko grafiko bat, zeinaren ertz bakoitzeko beharrezkoa den, adibidez, zenbaki osoek zehaztutako 2 ezaugarri gehigarri gordetzea. Kasu honetan, bere ondokotasun-bektorea "bikoteen" multzo ordenatu gisa defini daiteke, "laukoteen" baizik (a[2i], a[2i+1], a[2i+2], a. [2i+3]…) , non a[2i+2] eta a[2i+3] dagokion ertzaren ezaugarriak zehaztuko dituzten. Ertzen pisu osoak dituen grafiko baterako, ordena oro har antzekoa da (desberdintasun bakarra izango da atributuak ertzaren pisuari jarraituko diotela eta a[2i+3] eta a[2i+4] elementuek zehaztuko dutela. , eta ertza bera zehaztuko da ez 4, 5 zenbaki ordenatu baizik). Eta ertz osoak ez diren pisuak dituen grafiko baterako, ezaugarriak haztatu gabeko osagaian idatz daitezke.
Ertz osoko pisuak dituzten grafikoetarako ondokotasun-matrize asoziatiboa erabiltzen denean, posible da balio gisa zehaztea ez zenbaki bakar bat, baizik eta ertz baten pisuaz gain, beharrezkoak diren gainerako guztiak zehazten dituen zenbaki-matrizea (bektorea). Ezaugarriak. Aldi berean, oso-osorik ez duten pisuen kasuan eragozpen bat koma mugikorreko zenbakidun zeinu bat zehaztu beharra izango da (bai, eragozpena da, baina halako zeinu asko ez badira, eta ez baduzu. Ez jarri bikoitz “delikatuak”egiak, baliteke ezer ez izatea). Horrek esan nahi du C++-n ondokotasun-matrize asoziatibo hedatuak honela definitu daitezkeela: std::map , std::vector> edo std::map , std::vector, zeinetan "gako-balio-bektorea"-ko lehen balioa ertzaren pisua izango den, eta ondoren bere ezaugarrien zenbakizko izendapenak kokatzen dira.
Literatura:
Grafikoei eta algoritmoei buruz, oro har:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmoak: eraikuntza eta analisia, 2. edizioa: Trans. ingelesetik – M.: Williams argitaletxea, 2011.
2. Harari Frank. Grafikoen teoria. M.: Mir, 1973.
Egilearen txostena bektore eta elkartze-matrize hauei buruz:
3. Txernoukhov S.A. Aldakortasun-bektorea eta elkartze-matrizea grafikoak irudikatzeko eta gordetzeko modu gisa / SA Chernouhov. Albokotasun-bektorea eta aldameneko mapa grafiko bat irudikatzeko datu-egitura gisa // Nazioarteko Zientzia eta Praktiko Konferentziako artikulu bilduma "Problems of implementing the results of innovative developments and ways to solve them" (Saratov, 14.09.2019ko irailaren 2019a). – Sterlitamak: AMI, 65, or. 69-XNUMX
Gaiari buruzko sareko iturri erabilgarriak:
4.
5.
Iturria: www.habr.com