Saluton
En ĉi tiu noto, mi decidis listigi la ĉefajn datumstrukturojn uzatajn por stoki grafikaĵojn en komputiko, kaj mi ankaŭ parolos pri kelkaj pli da tiaj strukturoj, kiuj iel "kristaliĝis" por mi.
Do, ni komencu. Sed ne dekomence - mi pensas, ke ni ĉiuj jam scias kio estas grafeo kaj kio ili estas (direktita, nedirektita, pezbalancita, nepezigita, kun aŭ sen multoblaj randoj kaj bukloj).
Do, ni iru. Kiajn eblojn por datumstrukturoj por "grafa stokado" ni havas?
1. Matricaj datumstrukturoj
1.1 Apudmatrico. La apuda matrico estas matrico kie la vicoj kaj kolumnaj titoloj respondas al la nombroj de la verticoj de la grafeo, kaj la valoro de ĉiu el ĝiaj elementoj a(i,j) estas determinita de la ĉeesto aŭ foresto de randoj inter verticoj. i kaj j (estas klare, ke por nedirektita grafeo tia matrico estos simetria, aŭ ni povas konsenti, ke ni stokas ĉiujn valorojn nur super la ĉefa diagonalo). Por nepezigitaj grafeoj, a(i,j) povas esti agordita per la nombro da randoj de i ĝis j (se ne ekzistas tia rando, tiam a(i,j)= 0), kaj por pezbalancitaj grafeoj, ankaŭ per la pezo (totala pezo) de la menciitaj randoj.
1.2 Incidmatrico. En ĉi tiu kazo, nia grafeo ankaŭ estas konservita en tabelo en kiu, kiel regulo, la vico-nombroj respondas al la nombroj de ĝiaj verticoj, kaj la kolumnombroj respondas al antaŭ-numeritaj randoj. Se vertico kaj rando estas okazantaj unu al la alia, tiam ne-nula valoro estas skribita en la ekvivalenta ĉelo (por nedirektaj grafeoj, 1 estas skribita se la vertico kaj rando estas okazantaj, por orientitaj grafeoj - "1" se la rando "eliras" el la vertico kaj "-1" se ĝi "inkludas" en ĝi (estas sufiĉe facile memori, ĉar ankaŭ la signo "minuso" ŝajnas esti "inkludita" en la nombro "-1"). Por pezigitaj grafikaĵoj, denove, anstataŭ 1 kaj -1, vi povas specifi la totalan pezon de la rando.
2. Nombraj datumstrukturoj
2.1 Listo de apudeco. Nu, ĉio ŝajnas esti simpla ĉi tie. Ĉiu vertico de la grafeo povas, ĝenerale, esti asociita kun iu nombra strukturo (listo, vektoro, tabelo, ...), kiu stokos la nombrojn de ĉiuj verticoj najbaraj al la donita. Por direktitaj grafeoj, ni aldonos al tia listo nur tiujn verticojn al kiuj estas "direktita" rando de trajtovertico. Por pezbalancitaj grafeoj la efektivigo estos pli kompleksa.
2.2 Listo de ripoj. Sufiĉe populara datumstrukturo. La listo de randoj, kiel Captain Obviousness rakontas al ni, estas fakte listo de randoj de la grafeo, el kiuj ĉiu estas specifita per la komenca vertico, la finvertico (por nedirektaj grafeoj la ordo ne gravas ĉi tie, kvankam por unuiĝo oni povas uzu diversajn regulojn, ekzemple, specifi la verticojn en ordo pliiĝanta) kaj pezon (nur por pezigitaj grafeoj).
Vi povas rigardi la matriclistojn supre listigitajn pli detale (kaj kun ilustraĵoj), ekzemple, .
2.3 Najbara tabelo. Ne la plej ofta strukturo. Ĉe ĝia kerno, ĝi estas formo de "pakado" de apudeclistoj en unu liststrukturon (tabelo, vektoro). La unuaj n (laŭ la nombro da verticoj de la grafeo) elementoj de tia tabelo enhavas la komencajn indeksojn de la sama tabelo, komencante de kiuj ĉiuj verticoj najbaraj al la donita estas skribitaj en vico.
Ĉi tie mi trovis la plej kompreneblan (por mi mem) klarigon:
3. Apudvektoro kaj Asocia Apudeca Tablo
Montriĝis, ke la aŭtoro de ĉi tiuj linioj, ne estante profesia programisto, sed kiu periode okupiĝis pri grafikaĵoj, plej ofte traktis listojn de randoj. Efektive, estas oportune se la grafeo havas plurajn maŝojn kaj randojn. Kaj do, en evoluo de la klasikaj listoj de randoj, mi proponas atenti ilian "evoluo/branĉo/modifo/mutacio", nome: la apuda vektoro kaj la asocieca apuda tabelo.
3.1 Apudvektoro
Kazo (a1): nepezigita grafikaĵo
Ni nomos apudecvektoro por nepezigita grafeo ordigita aro de para nombro da entjeroj (a[2i], a[2i+1],..., kie i estas numerita c 0), en kiu ĉiu paro de nombroj estas a[2i], a[2i+1 ] specifas grafean randon inter la verticoj a[2i] kaj a[2i+1], respektive.
Ĉi tiu registra formato ne enhavas informojn pri ĉu la grafikaĵo estas direktita (ambaŭ opcioj estas eblaj). Kiam oni uzas la digrafformaton, la rando estas konsiderata kiel direktita de a[2i] al a[2i+1]. Ĉi tie kaj malsupre: por nedirektitaj grafeoj, se necese, postuloj por la ordo de registraj verticoj povas esti aplikitaj (ekzemple, ke la vertico kun la pli malalta valoro de la nombro al ĝi atribuita unue venu).
En C++, estas konsilinde specifi apudan vektoron uzante std::vector, tial la nomo de ĉi tiu datumstrukturo.
Kazo (a2): nepezigita grafeo, randaj pezoj estas entjeroj
Per analogio kun kazo (a1), ni nomas la apudan vektoron por laŭpezigita grafeo kun entjeraj randaj pezoj ordigita aro (dinamika tabelo) de nombroj (a[3i], a[3i+1], a[3i+2], ..., kie i estas numerita c 0), kie ĉiu "triopo" de nombroj a[3i], a[3i+1], a[3i+2] precizigas randon de la grafeo inter verticoj numeritaj a[3i] kaj a[3i+1], respektive, kaj la valoro a [3i+2] estas la pezo de ĉi tiu rando. Tia grafeo ankaŭ povas esti aŭ direktita aŭ ne.
Kazo (b): nepezigita grafeo, ne-entjeraj randaj pezoj
Ĉar estas maleble stoki heterogenajn elementojn en unu tabelo (vektoro), ekzemple, la sekva efektivigo estas ebla. La grafeo estas stokita en paro de vektoroj, en kiuj la unua vektoro estas la apuda vektoro de la grafeo sen precizigado de la pezoj, kaj la dua vektoro enhavas la ekvivalentajn pezojn (ebla efektivigo por C++: std::pair). ). Tiel, por rando difinita per paro de verticoj sub indeksoj 2i, 2i+1 de la unua vektoro, la pezo estos egala al la elemento sub indekso i de la dua vektoro.
Nu, kial tio ĉi estas necesa?
Nu, la aŭtoro de ĉi tiuj linioj trovis ĝin sufiĉe utila por solvi kelkajn problemojn. Nu, de formala vidpunkto, estos la jenaj avantaĝoj:
- La apuda vektoro, kiel iu alia "nombra" strukturo, estas sufiĉe kompakta, okupas malpli da memoro ol la apudecmatrico (por malabundaj grafeoj), kaj estas relative facila por efektivigi.
- La verticoj de la grafeo, principe, ankaŭ povas esti markitaj per negativaj nombroj. Kio se tia "perversio" estas bezonata?
- Grafikaĵoj povas enhavi plurajn randojn kaj multoblajn buklojn, kun malsamaj pezoj (pozitivaj, negativaj, eĉ nul). Ne estas limigoj ĉi tie.
- Vi ankaŭ povas asigni malsamajn ecojn al randoj - sed por pli pri tio, vidu sekcion 4.
Tamen, oni devas konfesi, ke ĉi tiu "listo" ne implicas rapidan aliron al la rando. Kaj ĉi tie la Asocia Najbara Tablo venas al la rekupero, kiu estas diskutita sube.
3.2 Asocia apuda tabelo
Do, se aliro al specifa rando, ĝia pezo kaj aliaj ecoj estas kritika por ni, kaj memorpostuloj ne permesas al ni uzi la apudan matricon, tiam ni pensu pri kiel ni povas ŝanĝi la apudan vektoron por solvi ĉi tiun problemon. Do, la ŝlosilo estas rando de la grafeo, kiu povas esti specifita kiel ordigita paro de entjeroj. Kiel ĉi tio aspektas? Ĉu ĝi ne estas ŝlosilo en asocia tabelo? Kaj, se jes, kial ni ne efektivigas ĝin? Ni havu asocian tabelon kie ĉiu ŝlosilo - ordigita paro de entjeroj - estos asociita kun valoro - entjero aŭ reala nombro kiu specifas la pezon de la rando. En C++, estas konsilinde efektivigi ĉi tiun strukturon bazitan sur la std::map-ujo (std::map , int> aŭ std::map , double>), aŭ std::multap se oni atendas plurajn randojn. Nu, ni havas strukturon por stoki grafeojn, kiu okupas malpli da memoro ol "matricaj" strukturoj, povas difini grafeojn kun multoblaj bukloj kaj randoj, kaj eĉ ne havas striktajn postulojn por la nenegativeco de verticaj nombroj (mi ne scias. kiu bezonas ĉi tion, sed tamen).
4. Datumaj strukturoj estas plenaj, sed io mankas
Kaj estas vero: solvante kelkajn problemojn, ni eble bezonos asigni iujn karakterizaĵojn al la randoj de la grafikaĵo kaj, sekve, konservi ilin. Se estas eble malambigue redukti ĉi tiujn trajtojn al entjeroj, tiam estas eble stoki tiajn "grafeojn kun kromaj trajtoj" uzante plilongigitajn versiojn de la apuda vektoro kaj asocieca apuda tabelo.
Do, ni havu nepezigitan grafeon, por ĉiu rando de kiu necesas konservi, ekzemple, 2 pliajn trajtojn specifitajn per entjeroj. En ĉi tiu kazo, eblas difini ĝian apudan vektoron kiel ordigitan aron ne de “paroj”, sed de “kvartetoj” de entjeroj (a[2i], a[2i+1], a[2i+2], a [2i+3]...) , kie a[2i+2] kaj a[2i+3] determinos la karakterizaĵojn de la responda rando. Por grafeo kun entjeraj pezoj de randoj, la ordo estas ĝenerale simila (la nura diferenco estos ke la atributoj sekvos la pezon de la rando kaj estos specifitaj per la elementoj a[2i+3] kaj a[2i+4] , kaj la rando mem estos specifita ne 4, sed 5 ordigitaj nombroj). Kaj por grafeo kun ne-entjeraj randaj pezoj, la trajtoj povas esti skribitaj en ĝian nepezigitan komponenton.
Kiam oni uzas asociecan apudan tabelon por grafikaĵoj kun entjeraj randaj pezoj, eblas specifi kiel valoron ne ununuran nombron, sed tabelon (vektoron) de nombroj, kiuj precizigas, krom la pezo de rando, ĉiujn ĝiajn aliajn necesajn. Trajtoj. Samtempe, ĝeno por la kazo de ne-entjeraj pezoj estos la bezono specifi signon kun glitkoma nombro (jes, ĉi tio estas ĝeno, sed se ne estas tiom da tiaj signoj, kaj se vi ne ne starigu ilin tro "delikataj" duoble, tiam eble estos nenio) . Ĉi tio signifas, ke en C++ etenditaj asociecaj apudecaj tabeloj povas esti difinitaj jene: std::map , std::vector> aŭ std::map , std::vector, en kiu la unua valoro en la "ŝlosilo-valor-vektoro" estos la pezo de la rando, kaj tiam la nombraj nomoj de ĝiaj karakterizaĵoj troviĝas.
Literaturo:
Pri grafikaĵoj kaj algoritmoj ĝenerale:
1. Cormen, Thomas H., Leiserson, Karlo la 2-a, Rivest, Ronald L., Stein, Clifford. Algoritmoj: konstruo kaj analizo, 2011-a eldono: Trad. el la angla – M.: Eldonejo Williams, XNUMX.
2. Harari Frank. Grafika teorio. M.: Mir, 1973.
La raporto de la aŭtoro pri ĉi tiuj sama vektoro kaj asocia aro de apudecoj:
3. Ĉernuĥov S.A. Apudvektoro kaj asocieca apudeco tabelo kiel manieroj reprezenti kaj stoki grafeojn / SA Chernouhov. Vektoro de apudeco kaj mapo de apudeco kiel datumstrukturoj por reprezenti grafeon // Kolekto de artikoloj de la Internacia Scienca kaj Praktika Konferenco "Problemoj por efektivigi la rezultojn de novigaj evoluoj kaj manieroj solvi ilin" (Saratov, 14.09.2019-a de septembro 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Utilaj interretaj fontoj pri la temo:
4.
5.
fonto: www.habr.com