Salama daholo.
Amin'ity naoty ity dia nanapa-kevitra ny hanao lisitra ireo rafitra angon-drakitra lehibe ampiasaina amin'ny fitahirizana grafika amin'ny siansa informatika aho, ary hiresaka momba ny rafitra roa toy izany ihany koa aho izay "nanjary kristaly" ho ahy.
Noho izany, andao hanomboka. Saingy tsy hatrany am-piandohana - Heveriko fa efa fantatry ny rehetra ny atao hoe grafofaonina sy ny maha-izy azy (directed, undirected, weighted, unweighted, misy sisiny sy tadivavarana maromaro na tsy misy).
Andeha àry. Inona no safidy ho an'ny rafitra angona ho an'ny "fitehirizana grafika" ananantsika?
1. Rafitra angona matrix
1.1 Adjacency matrix. Ny matrice mifanakaiky dia matrix izay mifanandrify amin'ny isan'ny vertices amin'ny grafika ny lohatenin'ny andalana sy ny tsanganana, ary ny sandan'ny singa tsirairay ao aminy a(i,j) dia faritana amin'ny fisian'ny sisiny eo anelanelan'ny vertices na tsy misy. i sy j (mazava fa ho an'ny grafika tsy mitongilana ny matrix toy izany dia ho symmetrical, na afaka manaiky isika fa mitahiry ny soatoavina rehetra eo ambonin'ny diagonal lehibe ihany). Ho an'ny grafika tsy misy lanja, ny a(i,j) dia azo apetraka amin'ny isan'ny sisiny manomboka amin'ny i ka hatramin'ny j (raha tsy misy sisiny toy izany, dia a(i,j)= 0), ary ho an'ny grafika mavesatra, ary koa amin'ny lanja. (lanja manontolo) amin'ny sisiny voalaza.
1.2 Matrix tranga. Amin'ity tranga ity, ny grafantsika dia voatahiry ao anaty tabilao iray izay matetika ny laharan'ny andalana dia mifanandrify amin'ny isan'ny vertices, ary ny laharan'ny tsanganana dia mifanitsy amin'ny sisiny efa misy laharana. Raha misy vertex sy sisiny iray mifanatrika, dia misy sanda tsy aotra voasoratra ao amin'ny sela mifanandrify (ho an'ny grafofa tsy mitongilana, 1 dia nosoratana raha toa ka zava-niseho ny vertex sy sisiny, ho an'ny grafika mitodika - "1" raha ny sisiny "fivoahana" avy amin'ny vertex sy "-1" raha "tafiditra" ao aminy (mora tadidy, satria ny famantarana "minus" koa dia toa "tafiditra" amin'ny isa "-1")). Ho an'ny grafika lanja indray, raha tokony ho 1 sy -1, dia azonao atao ny mamaritra ny totalin'ny lanjan'ny sisiny.
2. Rafitra angon-drakitra fanisana
2.1 Lisitra mifanakaiky. Eny, toa tsotra ny zava-drehetra eto. Ny vertex tsirairay amin'ny grafika amin'ny ankapobeny dia azo ampifandraisina amin'ny firafitry ny fanisana (lisitra, vector, array, ...), izay hitahiry ny isan'ny vertices rehetra mifanakaiky amin'ilay nomena. Ho an'ny grafika mivantana, dia ireo vertices izay misy sisiny "direction" avy amin'ny vertex endri-javatra ihany no ampianay ao anaty lisitra toy izany. Ho an'ny grafika misy lanjany dia ho sarotra kokoa ny fampiharana.
2.2 Lisitry ny taolan-tehezana. Firafitra angona malaza be. Ny lisitr'ireo sisiny, araka ny lazain'ny Kapiteny Obviousness amintsika, dia lisitr'ireo sisiny amin'ny grafika, ny tsirairay amin'izy ireo dia voafaritra amin'ny alàlan'ny vertex fanombohana, ny vertex farany (ho an'ny grafika tsy voarindra dia tsy zava-dehibe ny filaharana eto, na dia azonao atao aza ny mampiray. Mampiasà fitsipika isan-karazany, ohatra, mamaritra ny vertices amin'ny filaharan'ny fitomboana) sy ny lanjany (ho an'ny grafika lanja ihany).
Azonao atao ny mijery ny lisitry ny matrix voatanisa etsy ambony amin'ny antsipiriany kokoa (sy miaraka amin'ny fanoharana), ohatra, .
2.3 Array mifanakaiky. Tsy ny rafitra mahazatra indrindra. Amin'ny fotony, dia endrika "famonoana" lisitra mifanakaiky amin'ny rafitra fanisana iray (array, vector). Ny singa n voalohany (araka ny isan'ny vertices amin'ny grafika) amin'ny array toy izany dia misy tondro fanombohana an'io laharan-tariby io, manomboka amin'ny fanoratana ny vertices rehetra mifanila amin'ilay nomena.
Eto aho dia nahita ny fanazavana azo takarina indrindra (ho an'ny tenako):
3. Vector Adjacency sy Array Adjacency Associative
Hita fa ny mpanoratra an'ireo andalana ireo, dia tsy programmer matihanina, fa nikarakara grafika tsindraindray, matetika no niresaka ny lisitry ny sisiny. Tena mety tokoa raha misy tadivavarana sy sisiny maromaro ny kisary. Ary noho izany, amin'ny fampivoarana ny lisitry ny sisiny mahazatra, dia manoro hevitra aho ny handinika ny "fampandrosoana / sampana / fanovana / mutation", izany hoe: ny vector mifanakaiky sy ny array mifanakaiky.
3.1 Vector mifanakaiky
Tranga (a1) : sary tsy misy lanja
Hantsoinay ny véktora mifanakaiky ho an'ny grafika tsy misy lanja ho andiana isa mitovy isa (a[2i], a[2i+1],..., izay misy isa i c 0), izay misy isa roa. dia a[2i], a[2i+1 ] dia mamaritra ny sisiny grafika eo anelanelan'ny vertices a[2i] sy a[2i+1] tsirairay avy.
Ity endrika fandraketana ity dia tsy misy fampahafantarana momba ny hoe mizotra ny kisary (azo atao ny safidy roa). Rehefa mampiasa ny endrika digraph, ny sisiny dia heverina ho tarihina avy amin'ny [2i] mankany amin'ny [2i+1]. Eto sy eto ambany: ho an'ny kisary tsy misy toromarika, raha ilaina, dia azo ampiharina ny fepetra momba ny filaharan'ny fandraketana ny vertices (ohatra, fa ny vertex manana sanda ambany kokoa amin'ny isa nomena azy no voalohany).
Ao amin'ny C ++, tsara ny mamaritra ny véctor adjacency amin'ny fampiasana std::vector, noho izany ny anaran'ity rafitra data ity.
Tranga (a2) : tabilao tsy misy lanja, integer ny lanjan'ny sisiny
Amin'ny alàlan'ny fanoharana amin'ny tranga (a1), dia antsoinay ny véctor adjacency ho an'ny grafika mavesatra miaraka amin'ny lanjan'ny integer ho an'ny isa (a [3i], a[3i+1], a[3i+2], ..., izay misy isa i c 0), izay ahitana ny “triplet” tsirairay amin'ny isa a[3i], a[3i+1], a[3i+2] dia mamaritra ny sisin'ny kisary eo anelanelan'ny vertices misy laharana a[3i] ary ny a[3i+1], ary ny sanda a [3i+2] dia ny lanjan'io sisiny io. Ny grafika toy izany koa dia azo tarihina na tsia.
Tranga (b): tabilao tsy misy lanja, lanja tsy misy integer
Satria tsy azo atao ny mitahiry singa heterogène amin'ny array iray (vector), ohatra, azo atao ny fampiharana manaraka. Ny graphe dia voatahiry ao anaty vectors roa, izay ny vector voalohany dia ny vector mifanakaiky amin'ny grafika nefa tsy mamaritra ny lanjany, ary ny véctor faharoa dia misy ny lanjany mifanaraka amin'izany (azo ampiharina amin'ny C++: std:: pair ). Noho izany, ho an'ny sisiny iray voafaritry ny vertices mpivady eo ambanin'ny fanondro 2i, 2i+1 amin'ny véctor voalohany, ny lanjany dia hitovy amin'ny singa eo ambanin'ny fanondro i an'ny vector faharoa.
Nahoana no ilaina izany?
Eny, hitan'ny mpanoratra an'ireo andalana ireo fa tena ilaina izy io amin'ny famahana olana maromaro. Eny, avy amin'ny fomba fijery ofisialy dia hisy ireto tombony manaraka ireto:
- Ny véctor adjacency, toy ny rafitra "enumerative" hafa rehetra, dia somary mirindra, maka fitadidiana kely kokoa noho ny matrix adjacency (ho an'ny grafika vitsy), ary mora ny mampihatra.
- Ny vertices amin'ny grafika, raha ny fitsipika, dia azo asiana isa ratsy ihany koa. Ahoana raha ilaina ny “fivadika” toy izany?
- Mety misy sisiny maromaro sy tadivavarana maromaro ny kisary, miaraka amin'ny lanja samihafa (tsara, ratsy, na aotra aza). Tsy misy famerana eto.
- Azonao atao ihany koa ny manendry fananana samihafa amin'ny sisiny - fa raha mila fanazavana fanampiny momba izany dia jereo ny fizarana 4.
Na izany aza, tsy maintsy ekena fa ity "lisitra" ity dia tsy midika ho fidirana haingana amin'ny sisiny. Ary eto ny Associative Adjacency Array dia tonga hamonjy, izay resahina etsy ambany.
3.2 Array mifanakaiky
Noho izany, raha ny fidirana amin'ny sisiny manokana, ny lanjany sy ny fananana hafa dia tena zava-dehibe ho antsika, ary ny fitadidiana fitadidiana dia tsy mamela antsika hampiasa ny matrix adjacency, dia andeha isika handinika ny fomba hanovana ny vector adjacency hamahana ity olana ity. Noho izany, ny lakile dia sisin'ny grafika, izay azo faritana ho toy ny mpivady integer. Manao ahoana izany? Tsy fanalahidin'ny array associative ve izany? Ary, raha eny, nahoana isika no tsy mampihatra izany? Andeha isika hanana laha-pikambanana izay ahafahan'ny fanalahidy tsirairay - ny isa maromaro voafaritry ny isa - dia hifandray amin'ny sanda iray - integer na isa tena izy izay mamaritra ny lanjan'ny sisiny. Ao amin'ny C ++, tsara ny mampihatra ity rafitra ity mifototra amin'ny std :: map container (std :: map , int> na std::map , double>), na std::multimap raha andrasana ny sisiny maromaro. Eny, manana rafitra fitehirizana grafika izay maka fitadidiana kely kokoa noho ny rafitra “matrix” isika, afaka mamaritra ny grafika misy tadivavarana sy sisiny maro, ary tsy manana fepetra hentitra akory amin'ny tsy negativity ny isa vertex (tsy fantatro. iza no mila an'ity, nefa mbola).
4. Feno ny rafitra data, saingy misy zavatra tsy ampy
Ary marina izany: rehefa mamaha olana maromaro isika dia mety mila manendry toetra sasantsasany amin'ny sisin'ny grafika ary, araka izany, dia mitahiry azy ireo. Raha azo atao ny mampihena amin'ny fomba mazava ireo endri-javatra ireo ho integer, dia azo atao ny mitahiry "sarisary misy endri-javatra fanampiny" toy izany amin'ny alàlan'ny dikan-teny miitatra amin'ny véctor adjacency sy array mifanakaiky.
Noho izany, andeha isika hanana grafika tsy misy lanjany, ho an'ny sisiny tsirairay izay ilaina ny mitahiry, ohatra, endri-javatra fanampiny 2 voatondro amin'ny isa. Amin'ity tranga ity, azo atao ny mamaritra ny véktora mifanakaiky azy ho toy ny andiana mibaiko tsy amin'ny "paires", fa "quartets" amin'ny isa (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , izay a[2i+2] sy a[2i+3] no mamaritra ny toetran'ny sisiny mifanitsy. Ho an'ny grafika misy lanja integer amin'ny sisiny, ny filaharana dia mitovy amin'ny ankapobeny (ny hany maha samy hafa dia ny hoe manaraka ny lanjan'ny sisiny ny toetra ary hofaritan'ny singa a[2i+3] sy a[2i+4] , ary ny sisiny dia tsy ho 4, fa laharana 5 voafaritry). Ary ho an'ny grafika misy lanja tsy misy integer dia azo soratana ao anatin'ny singa tsy lanjany ireo endri-javatra.
Rehefa mampiasa laharana mifanakaiky ho an'ny grafika misy lanja amin'ny sisiny integer, dia azo atao ny mamaritra ho sanda tsy isa tokana, fa laharana (vector) amin'ny isa izay mamaritra, ankoatry ny lanjan'ny sisiny, ny hafa rehetra ilaina. Toetoetra. Mandritra izany fotoana izany, ny tsy fahatomombanana amin'ny tranga tsy misy integer dia ilaina ny mamaritra famantarana miaraka amin'ny isa mitsingevana (eny, tsy mety izany, fa raha tsy misy famantarana toy izany, ary raha tsy 'aza apetraka ho "sarotra" avo roa heny izy ireo, dia mety ho tsinontsinona izany). Midika izany fa amin'ny C ++ dia azo faritana toy izao manaraka izao ny arrays adjacency associative: std::map , std::vector> na std::map , std::vector, izay ny sanda voalohany ao amin'ny "key-value-vector" dia ny lanjan'ny sisiny, ary avy eo dia misy ny fanondroana isa ny toetrany.
Haisoratra:
Momba ny grafika sy ny algorithm amin'ny ankapobeny:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithm: fanorenana sy fanadihadiana, andiany faha-2: Trans. avy amin'ny teny anglisy – M.: Williams Publishing House, 2011.
2. Harari Frank. Teolojia grafofaonina. M.: Mir, 1973.
Ny tatitry ny mpanoratra momba ireto vectors sy array associative adjacencies ireto ihany:
3. Chernoukhov S.A. Vector adjacency sy array adjacency associative ho fomba hanehoana sy fitehirizana sary / SA Chernouhov. Vector adjacency sy sarintany mifanakaiky ho firafitry ny angon-drakitra hanehoana grafika // Fanangonana lahatsoratra ao amin'ny International Scientific and Practical Conference "Olana amin'ny fampiharana ny vokatry ny fivoarana vaovao sy ny fomba hamahana azy ireo" (Saratov, 14.09.2019 septambra 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Loharano mahasoa amin'ny Internet momba ny lohahevitra:
4.
5.
Source: www.habr.com