Kumusta tanan.
Niini nga nota, nakahukom ko nga ilista ang mga nag-unang istruktura sa datos nga gigamit sa pagtipig sa mga graph sa siyensya sa kompyuter, ug maghisgot usab ako bahin sa usa ka magtiayon nga ingon nga mga istruktura nga sa usa ka paagi "nag-crystallize" alang kanako.
Busa, magsugod kita. Apan dili gikan sa sinugdanan - sa akong hunahuna kitang tanan nahibal-an na kung unsa ang usa ka graph ug kung unsa kini (gidirekta, wala gipunting, gibug-aton, wala’y gibug-aton, adunay o wala ang daghang mga sulud ug mga loop).
So, adto ta. Unsa nga mga kapilian alang sa mga istruktura sa datos alang sa "pagtipig sa grapika" ang naa kanato?
1. Mga istruktura sa datos sa matrix
1.1 Adjacency matrix. Ang adjacency matrix kay usa ka matrix diin ang row ug column nga mga ulohan katumbas sa mga numero sa vertices sa graph, ug ang bili sa matag usa sa mga elemento niini a(i,j) gitino pinaagi sa presensya o pagkawala sa mga sidsid tali sa vertices. i ug j (klaro nga alang sa usa ka dili direkta nga graph ang ingon nga usa ka matrix mahimong simetriko, o kita magkauyon nga atong tipigan ang tanan nga mga bili lamang sa ibabaw sa main diagonal). Alang sa dili timbang nga mga graph, ang a(i,j) mahimong itakda pinaagi sa gidaghanon sa mga sidsid gikan sa i ngadto sa j (kon walay ingon nga sidsid, nan a(i,j)= 0), ug alang sa gibug-aton nga mga graph, usab sa gibug-aton (kinatibuk-ang gibug-aton) sa gihisgutan nga mga ngilit.
1.2 Matrix sa insidente. Sa kini nga kaso, ang among graph gitipigan usab sa usa ka lamesa diin, ingon nga usa ka lagda, ang mga numero sa laray katumbas sa mga numero sa mga vertices niini, ug ang mga numero sa kolum katumbas sa pre-numbered nga mga ngilit. Kung ang usa ka vertex ug usa ka ngilit mahitabo sa usag usa, unya usa ka dili-zero nga kantidad ang isulat sa katugbang nga cell (alang sa dili direkta nga mga graph, ang 1 gisulat kung ang vertex ug ngilit usa ka insidente, alang sa gipunting nga mga graph - "1" kung ang ngilit Ang "exit" gikan sa vertex ug "-1" kung kini "naglakip" niini (kini igo nga mahinumduman, tungod kay ang "minus" nga timaan ingon usab "gilakip" sa numero nga "-1")). Alang sa gibug-aton nga mga graph, pag-usab, imbes nga 1 ug -1, mahimo nimong ipiho ang kinatibuk-ang gibug-aton sa ngilit.
2. Mga istruktura sa datos sa pag-ihap
2.1 Listahan sa kasikbit. Aw, morag simple ra ang tanan dinhi. Ang matag vertex sa graph mahimo, sa kinatibuk-an, i-uban sa bisan unsang enumeration structure (lista, vector, array, ...), nga magtipig sa mga numero sa tanang vertices nga kasikbit sa gihatag. Alang sa mga gidirekta nga mga graph, among idugang sa ingon nga usa ka lista lamang ang mga vertices diin adunay "gidirekta" nga ngilit gikan sa usa ka feature vertex. Alang sa gibug-aton nga mga graph ang pagpatuman mahimong mas komplikado.
2.2 Listahan sa mga gusok. Usa ka popular nga istruktura sa datos. Ang lista sa mga ngilit, ingon sa gisulti ni Kapitan Obviousness, sa tinuud usa ka lista sa mga ngilit sa graph, nga ang matag usa gipiho sa pagsugod nga vertex, ang katapusan nga vertex (alang sa wala gipunting nga mga graph dili hinungdanon ang han-ay dinhi, bisan kung mahimo nimo ang paghiusa. gamita ang lain-laing mga lagda, pananglitan, pagpiho sa mga vertices sa pagkasunod-sunod nga pagtaas) ug gibug-aton (alang sa gibug-aton nga mga graph lamang).
Mahimo nimong tan-awon ang mga lista sa matrix nga gilista sa ibabaw sa mas detalyado (ug adunay mga ilustrasyon), pananglitan, .
2.3 Adjacency array. Dili ang labing komon nga istruktura. Sa kinauyokan niini, kini usa ka porma sa "pagputos" sa mga lista sa kasikbit ngadto sa usa ka enumeration structure (array, vector). Ang una nga n (sumala sa gidaghanon sa mga vertices sa graph) nga mga elemento sa ingon nga array naglangkob sa mga pagsugod nga indeks sa parehas nga array, sugod diin ang tanan nga vertices nga kasikbit sa gihatag nga usa gisulat sa usa ka laray.
Dinhi akong nakit-an ang labing masabtan (alang sa akong kaugalingon) nga katin-awan:
3. Adjacency Vector ug Associative Adjacency Array
Nahibal-an nga ang tagsulat niini nga mga linya, dili usa ka propesyonal nga programmer, apan kanunay nga nag-atubang sa mga graph, kanunay nga naghisgot sa mga lista sa mga sulud. Sa pagkatinuod, kini sayon kon ang graph adunay daghang mga galong ug mga kilid. Ug busa, sa pagpauswag sa mga klasiko nga lista sa mga ngilit, gisugyot nako nga hatagan pagtagad ang ilang "pag-uswag / sanga / pagbag-o / mutation", nga mao: ang adjacency vector ug ang associative adjacency array.
3.1 Adjacency vector
Kaso (a1): dili timbang nga graph
Tawgon nato ang adjacency vector para sa unweighted graph nga usa ka ordered set sa usa ka even number of integers (a[2i], a[2i+1],..., diin ang i gi-numero c 0), diin ang matag parisan sa mga numero. a[2i], a[2i+1 ] nagtino sa usa ka graph nga ngilit tali sa vertices a[2i] ug a[2i+1], matag usa.
Kini nga format sa pagrekord wala maglangkob sa kasayuran kung ang graph gidirekta (ang duha nga kapilian mahimo). Kung gamiton ang format sa digraph, ang ngilit giisip nga gipunting gikan sa usa [2i] hangtod sa usa [2i + 1]. Dinhi ug sa ubos: alang sa mga dili direkta nga mga graph, kung gikinahanglan, ang mga kinahanglanon alang sa han-ay sa pagrekord sa mga vertices mahimong magamit (pananglitan, nga ang vertex nga adunay mas ubos nga kantidad sa numero nga gi-assign niini mao ang una).
Sa C++, maayo nga magbutang ug adjacency vector gamit ang std::vector, busa ang ngalan niini nga data structure.
Kaso (a2): dili timbang nga graph, ang mga gibug-aton sa kilid integer
Pinaagi sa analogy sa case (a1), gitawag nato ang adjacency vector para sa usa ka weighted graph nga adunay integer edge weights nga usa ka ordered set (dynamic array) sa mga numero (a[3i], a[3i+1], a[3i+2], ..., diin ang i gi-numero nga c 0), diin ang matag "triplet" sa mga numero a[3i], a[3i+1], a[3i+2] nagtino sa usa ka ngilit sa graph tali sa mga vertices nga gi-numero nga a[3i] ug a[3i+1], matag usa, ug ang bili a [3i+2] mao ang gibug-aton niini nga ngilit. Ang ingon nga graph mahimo usab nga idirekta o dili.
Case (b): dili timbang nga graph, dili integer nga mga gibug-aton sa kilid
Tungod kay imposible nga tipigan ang mga heterogenous nga elemento sa usa ka array (vector), pananglitan, posible ang mosunod nga pagpatuman. Ang graph gitipigan sa usa ka pares sa mga vector, diin ang unang vector mao ang adjacency vector sa graph nga walay pagtino sa mga gibug-aton, ug ang ikaduha nga vector naglangkob sa katugbang nga mga gibug-aton (posible nga pagpatuman alang sa C++: std:: pares ). Busa, alang sa usa ka sidsid nga gihubit sa usa ka parisan sa vertices ubos sa mga indeks 2i, 2i+1 sa unang vector, ang gibug-aton mahimong katumbas sa elemento ubos sa indeks i sa ikaduhang vector.
Aw, nganong gikinahanglan kini?
Aw, ang tagsulat niini nga mga linya nakit-an nga kini mapuslanon alang sa pagsulbad sa daghang mga problema. Aw, gikan sa usa ka pormal nga punto sa panglantaw, adunay mga mosunod nga mga bentaha:
- Ang adjacency vector, sama sa bisan unsang lain nga "enumerative" nga istruktura, medyo compact, gamay ra ang memorya kaysa sa adjacency matrix (para sa mga gamay nga graph), ug medyo dali nga ipatuman.
- Ang mga vertices sa graph, sa prinsipyo, mahimo usab nga markahan sa negatibo nga mga numero. Unsa kaha kon gikinahanglan ang maong “pagtuis”?
- Ang mga graph mahimong adunay daghang mga sidsid ug daghang mga loop, nga adunay lainlaing mga gibug-aton (positibo, negatibo, bisan zero). Walay mga pagdili dinhi.
- Mahimo usab nimong i-assign ang lainlaing mga kabtangan sa mga sulud - apan alang sa dugang bahin niana, tan-awa ang seksyon 4.
Bisan pa, kinahanglan nga dawaton nga kini nga "listahan" wala magpasabut nga dali nga pag-access sa sulud. Ug dinhi ang Associative Adjacency Array moabut sa pagluwas, nga gihisgutan sa ubos.
3.2 Kauban nga kadugtong nga han-ay
Busa, kung ang pag-access sa usa ka piho nga sidsid, ang gibug-aton niini ug uban pang mga kabtangan hinungdanon alang kanamo, ug ang mga kinahanglanon sa panumduman wala magtugot kanamo sa paggamit sa adjacency matrix, nan atong hunahunaon kung giunsa naton mabag-o ang adjacency vector aron masulbad kini nga problema. Busa, ang yawe mao ang usa ka ngilit sa graph, nga mahimong espesipiko ingon usa ka gimando nga pares sa mga integer. Unsay hitsura niini? Dili ba kini usa ka yawe sa usa ka associative array? Ug, kung mao, nganong dili nato kini ipatuman? Magbaton kita og associative array diin ang matag yawe - usa ka ordered pair of integers - mag-uban sa usa ka value - usa ka integer o tinuod nga numero nga nagtino sa gibug-aton sa sidsid. Sa C++, maayo nga ipatuman kini nga istruktura base sa std :: map container (std :: map , int> o std::map , double>), o std::multimap kung daghang mga kilid ang gilauman. Aw, kita adunay usa ka istruktura alang sa pagtipig sa mga graph nga nagkinahanglan og gamay nga memorya kay sa "matrix" nga mga istruktura, makahubit sa mga graph nga adunay daghang mga galong ug mga ngilit, ug wala'y higpit nga mga kinahanglanon alang sa dili negatibo nga mga numero sa vertex (wala ko kahibalo kinsa nagkinahanglan niini, apan sa gihapon).
4. Ang mga istruktura sa datos puno, apan adunay kulang
Ug kini tinuod: sa pagsulbad sa usa ka gidaghanon sa mga problema, kita kinahanglan nga mag-assign sa pipila ka mga kinaiya ngadto sa mga ngilit sa graph ug, sumala niana, tipigi kini. Kung posible nga makunhuran ang kini nga mga bahin sa mga integer, nan posible nga tipigan ang ingon nga "mga graph nga adunay dugang nga mga bahin" gamit ang mga pinalawig nga bersyon sa adjacency vector ug associative adjacency array.
Busa, kita adunay usa ka dili timbang nga graph, alang sa matag ngilit diin kini kinahanglan nga tipigan, pananglitan, 2 nga dugang nga mga bahin nga gitino sa mga integer. Sa kini nga kaso, posible nga ipatin-aw ang adjacency vector niini isip usa ka ordered set dili sa "pares", apan sa "quartets" sa mga integer (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , diin ang a[2i+2] ug a[2i+3] maoy magtino sa mga kinaiya sa katugbang nga ngilit. Alang sa usa ka graph nga adunay integer nga gibug-aton sa mga sidsid, ang han-ay sa kasagaran parehas (ang kalainan mao nga ang mga kinaiya mosunod sa gibug-aton sa sidsid ug ipiho sa mga elemento a [2i+3] ug a[2i+4] , ug ang ngilit mismo ipiho dili 4, apan 5 nga gi-order nga mga numero). Ug alang sa usa ka graph nga adunay dili-integer nga mga gibug-aton sa sulab, ang mga bahin mahimong isulat sa dili timbang nga bahin niini.
Kung naggamit ug associative adjacency array para sa mga graph nga adunay integer edge nga gibug-aton, posible nga ipiho isip usa ka bili nga dili usa ka numero, apan usa ka array (vector) sa mga numero nga nagtino, dugang pa sa gibug-aton sa usa ka sidsid, ang tanan nga gikinahanglan. mga bahin. Sa parehas nga oras, ang usa ka kahasol alang sa kaso sa non-integer nga mga gibug-aton mao ang kinahanglan nga ipiho ang usa ka timaan nga adunay numero nga naglutaw nga punto (oo, kini usa ka kahasol, apan kung wala’y daghang ingon nga mga timailhan, ug kung wala ka 'ayaw sila ibutang nga "makalilisang" nga doble, unya mahimo nga wala'y bisan unsa) . Kini nagpasabot nga sa C++ gipalugwayan nga associative adjacency arrays mahimong mahubit sama sa mosunod: std::map , std::vector> o std::map , std::vector, diin ang unang bili sa "key-value-vector" mao ang gibug-aton sa sidsid, ug unya ang mga numerical designations sa mga kinaiya niini nahimutang.
Literatura:
Mahitungod sa mga graph ug algorithm sa kinatibuk-an:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithm: pagtukod ug pagtuki, 2nd edisyon: Trans. gikan sa English – M.: Williams Publishing House, 2011.
2. Harari Frank. Teorya sa graph. M.: Mir, 1973.
Ang report sa tagsulat bahin niining parehas nga vector ug associative array of adjacencies:
3. Chernoukhov S.A. Adjacency vector ug associative adjacency array isip mga paagi sa pagrepresentar ug pagtipig sa mga graph / SA Chernouhov. Adjacency vector ug adjacency map isip mga istruktura sa datos nga magrepresentar sa usa ka graph // Koleksyon sa mga artikulo sa International Scientific and Practical Conference "Mga problema sa pagpatuman sa mga resulta sa mga bag-ong kalamboan ug mga paagi sa pagsulbad niini" (Saratov, Setyembre 14.09.2019, 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Mapuslanon nga mga tinubdan sa online sa hilisgutan:
4.
5.
Source: www.habr.com