Hê her kesî
Di vê têbînîyê de, min biryar da ku strukturên daneya bingehîn ên ku ji bo hilanîna grafikan di zanistiya computer de têne bikar anîn navnîş bikim, û ez ê li ser çend strukturên weha yên ku bi rengekî ji min re "kristalî" bûne jî biaxivim.
Ji ber vê yekê, em dest pê bikin. Lê ne ji destpêkê de - ez difikirim ku em hemî jixwe dizanin ku grafiyek çi ye û ew çi ne (rêber, nerasterî, giranî, negirandî, bi gelek kevroşk û lûkan an bêyî).
Ji ber vê yekê, em herin. Ji bo strukturên daneyê yên ji bo "depokirina grafîkê" çi vebijarkên me hene?
1. Avahiyên daneyên matrixê
1.1 Matrixa cîrantiyê. Matrixa cîrantiyê matrixek e ku tê de sernavên rêz û stûn bi hejmarên xalên grafîkê re têkildar e, û nirxa her hêmanên wê a(i,j) ji hêla hebûn an nebûna keviyan di navbera risteyan de tê destnîşankirin. i û j (eşkere ye ku ji bo grafiyek bêserûber matrixek wusa dê simetrîk be, an jî em dikarin bipejirînin ku em hemî nirxan tenê li jorê diagonala sereke hilînin). Ji bo grafikên negiran, a(i,j) dikare bi hejmara kenarê ji i heta j were danîn (eger tixûbek weha tunebe, wê demê a(i,j)= 0), û ji bo grafikên giranbiha jî bi giraniyê. (giraniya giştî) keviyên navborî.
1.2 Matrixa bûyeran. Di vê rewşê de, grafiya me jî di tabloyek ku tê de, wekî qaîdeyek, hejmarên rêzan bi hejmarên berikên wê re têkildar in, û hejmarên stûnê jî bi keviyên pêş-hejmarkirî re têkildar in, tê hilanîn. Ger ristek û xêzek bi hevûdu re rûbirû bin, wê hingê di şaneya têkildar de nirxek ne-sifir tê nivîsandin (ji bo grafikên nerasterê, 1 tê nivîsandin heke lûtk û xêv bi hev veqetin, ji bo yên arastekirî - "1" heke keviya "Derketin" ji deqê û "-1" heke "tevî" tê de (jibîrkirin bes hêsan e, ji ber ku nîşana "minus" jî di hejmara "-1" de "tevlî" xuya dike)). Ji bo grafikên giran, dîsa, li şûna 1 û -1, hûn dikarin giraniya tevayî ya qiraxê diyar bikin.
2. Avahiyên daneyên hejmartinê
2.1 Lîsteya cîrantiyê. Welê, her tişt li vir hêsan xuya dike. Bi gelemperî, her ristek grafîkê dikare bi her avahiyek hejmartinê (lîste, vektor, rêzik, ...) ve were girêdan, ku dê jimareyên hemî xalên li tenişta viya tomar bike. Ji bo grafikên rênîşander, em ê tenê wan lûtkeyan ku ji xêzek taybetmendiyê deqek "rêber" heye, li navnîşek wusa zêde bikin. Ji bo grafikên giran, pêkanîn dê tevlihevtir be.
2.2 List of ribs. Avahiya daneya pir populer. Lîsteya keviyan, wekî ku Captain Obviousness ji me re dibêje, bi rastî navnîşek kenarên grafîkê ye, ku her yek ji wan ji hêla vekêşa destpêkê, xala dawîn ve hatî destnîşan kirin (ji bo grafikên nerasterê rêzik li vir ne girîng e, her çend ji bo yekbûnê hûn dikarin qaîdeyên cihêreng bikar bînin, mînakî, diyarkirina risteyan li gorî mezinbûnê) û giraniyê (tenê ji bo grafikên girankirî).
Hûn dikarin li navnîşên matrixê yên ku li jor hatine destnîşan kirin bi hûrgulî (û bi nîgaran) binihêrin, mînakî, .
2.3 Array cîrantiyê. Ne avahiya herî gelemperî. Di bingeha xwe de, ew rengek "pakkirina" lîsteyên cîrantiyê di nav yek strukturek hejmartinê de ye (array, vektor). n-ya pêşîn (li gorî hejmara berikên grafîkê) hêmanên rêzikek weha nîşaneyên destpêkê yên heman rêzê vedihewîne, ku jê dest pê dike, hemî lûtkeyên li tenişta grafîkê di rêzê de têne nivîsandin.
Li vir min raveya herî têgihîştî (ji bo xwe) dît:
3. Vektora cîrantiyê û Arrayiya cîrantiyê ya komelî
Derket holê ku nivîskarê van rêzikan, ne bernamesazek profesyonel e, lê ku bi periyodîk bi grafîkan re mijûl dibe, pir caran bi navnîşên kevanan re mijûl dibe. Bi rastî, ew hêsan e ku grafîk xwedan lûk û keviya pirjimar be. Ji ber vê yekê, di pêşkeftina navnîşên klasîk ên kevanan de, ez pêşniyar dikim ku balê bikişînim ser "pêşveçûn / şax / guheztin / mutasyona wan", ango: vektora cîrantiyê û rêzika cîrantiyê ya têkildar.
3.1 Vektora cîrantiyê
Mesele (a1): grafiya negirandî
Em ê ji bo grafek negirandî vektora cîrantiyê bibêjin komek rêzkirî ya hejmareke zewacê (a[2i], a[2i+1],..., ku i bi c 0 tê hejmartin), ku tê de her cotek hejmar tê de a[2i] ye, a[2i+1] bi rêzê ve qiraxa grafikê ya di navbera xalên a[2i] û a[2i+1] de diyar dike.
Vê formata tomarkirinê agahdarî li ser rêwerziya grafîkê nagire (her du vebijark mimkun in). Dema ku forma digrafê bikar bînin, qerax ji a[2i] ber bi a[2i+1] ve tê hesibandin. Li vir û li jêr: ji bo grafikên nerasterê, heke hewce be, hewcedariyên ji bo rêza tomarkirina lûtkeyan dikarin werin sepandin (mînak, ku vertîka bi nirxa jêrîn a hejmara ku jê re hatî veqetandin tê pêşîn).
Di C++ de, tê pêşniyar kirin ku meriv vektorek cîrantiyê bi karanîna std:: vector diyar bike, ji ber vê yekê navê vê avahiya daneyê ye.
Rewşa (a2): grafiya negirandî, giraniya kêlekê jimar in
Bi analojiya rewşa (a1), em ji vektora cîrantiyê re ji bo grafek giranbiha ya bi giraniya hejmaran re dibêjin komek rêzkirî (saziya dînamîkî) ya hejmaran (a[3i], a[3i+1], a[3i+2], ..., cihê ku i bi c 0 tê hejmartin), ku her "sêqat" jimareyên a[3i], a[3i+1], a[3i+2] di navbera xalên bi jimareya a[3i] de qiraxa grafîkê diyar dike. û a[3i+1], bi rêzê ve, û nirxa a [3i+2] giraniya vê qiraxê ye. Grafikek weha jî dikare were rêve kirin an na.
Rewşa (b): grafiya negirandî, giraniya qiraxa ne-hejmar
Ji ber ku ne gengaz e ku hêmanên heterojen di yek rêzek (vektor) de werin hilanîn, mînakî, pêkanîna jêrîn gengaz e. Grafîk di cotek vektoran de tê hilanîn, ku vektora yekem vektora cîrantiya grafê ye bêyî ku giranan diyar bike, û vektora duyemîn giraniyên têkildar dihewîne (pêkanîna gengaz ji bo C++: std:: cot ). Ji ber vê yekê, ji bo qeraxa ku bi cotek vektora di bin îndeksên 2i, 2i+1 vektora yekem de hatî destnîşan kirin, giranî dê bi hêmana di binê nîşana i ya vektora duyemîn de wekhev be.
Baş e, çima ev pêwîst e?
Welê, nivîskarê van rêzan ew ji bo çareserkirina gelek pirsgirêkan pir kêrhatî dît. Welê, ji nêrînek fermî, dê avantajên jêrîn hebin:
- Vektora cîrantiyê, mîna her avahiyek din a "hejmarkirî", têra xwe tevlihev e, ji matrixa cîrantiyê kêmtir bîranînê digire (ji bo grafikên kêm), û bi rêkûpêk pêkanîna wê hêsan e.
- Berikên grafîkê, di prensîbê de, dikarin bi hejmarên neyînî jî bêne nîşankirin. Ger hewcedariyek weha "xerabî" hebe?
- Grafîk dikarin çend kevî û gelek lûpkan, bi giraniyên cihêreng (erênî, neyînî, hetta sifir) hebin. Li vir ti astengî tune.
- Her weha hûn dikarin taybetmendiyên cihêreng li qeraxan bidin - lê ji bo bêtir li ser wê, li beşa 4-ê binêre.
Lêbelê, pêdivî ye ku were pejirandin ku ev "lîste" nayê wateya gihîştina bilez a berbi. Û li vir Array Adjacency Associative ji bo rizgariyê tê, ku li jêr tê nîqaş kirin.
3.2 Rêzeya cîrantiya komelî
Ji ber vê yekê, heke gihîştina berbiyek taybetî, giraniya wê û taybetmendiyên din ji bo me krîtîk e, û hewcedariyên bîranînê nahêlin ku em matrixa cîrantiyê bikar bînin, wê hingê em bifikirin ka em çawa dikarin vektora cîrantiyê biguhezînin da ku vê pirsgirêkê çareser bikin. Ji ber vê yekê, miftek qiraxa grafikê ye, ku dikare wekî cotek rêzkirî ya jimareyan were destnîşan kirin. Ev çawa xuya dike? Ma ew ne mifteyek di rêzek hevgirtî de ye? Û, heke wusa ye, çima em wê bicîh nakin? Bihêle em arrayek hevedudanî hebe ku her kilît - cotek hejmarên rêzkirî - dê bi nirxek re têkildar be - hejmarek an jimarek rastîn a ku giraniya keviya diyar dike. Di C++ de, tê pêşniyar kirin ku vê strukturê li ser bingeha std:: konteynerê nexşeyê (std:: map , int> an jî std::nexşe , duqat>), an jî std::multimap heke çend keviyan li bendê bin. Welê, me avahiyek ji bo hilanîna grafiyan heye ku ji strukturên "matrîksê" kêmtir bîra digire, dikare grafikên bi pir lûl û kevanan diyar bike, û ji bo neneyînîbûna hejmarên vertexê jî hewcedariyên hişk tune (ez nizanim kê hewceyê vê yekê ye, lê dîsa jî).
4. Avahiyên daneyan tije ne, lê tiştek winda ye
Û ev rast e: dema ku hejmarek pirsgirêkan çareser dikin, dibe ku em hewce bikin ku hin taybetmendiyan li kêlekên grafîkê veqetînin û, li gorî vê yekê, wan hilînin. Ger gengaz e ku meriv van taybetmendiyan bi rengekî nezelal kêm bike ji hejmarên bêkêmasî, wê hingê gengaz e ku meriv "grafikên bi taybetmendiyên pêvek" ên weha bi karanîna guhertoyên dirêjkirî yên vektora cîrantiyê û rêzika cîrantiyê ya hevgirtî hilîne.
Ji ber vê yekê, bila ji me re grafiyek negiran hebe, ji bo her keviya wê pêdivî ye ku, mînakî, 2 taybetmendiyên din ên ku ji hêla jimaran ve hatine destnîşankirin werin hilanîn. Di vê rewşê de, mimkun e ku vektora cîrantiya wê wekî komek rêzkirî ne ji "cotan"an, lê ji "çartetan" yên hejmaran (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , ku a[2i+2] û a[2i+3] dê taybetmendiyên keviya têkildar diyar bikin. Ji bo grafiyek bi giraniya hejmaran, rêzik bi gelemperî dişibin hev (cudahiya tenê dê ev be ku taybetmendî dê li dû giraniya keviya bin û dê ji hêla hêmanên a[2i+3] û a[2i+4] ve bêne diyar kirin. , û qeraxa xwe dê ne 4, lê 5 hejmarên rêzkirî were destnîşan kirin). Û ji bo grafîkek bi giraniya kêleka ne-hejmar, taybetmendî dikarin di beşa wê ya negiran de bêne nivîsandin.
Dema ku ji bo grafikên bi giraniya kêlekê jimareyek hevgirtî tê bikar anîn, meriv dikare wekî nirxek ne hejmareke yek, lê rêzek (vektor) jimareyan diyar bike ku, ji bilî giraniya qeraxekê, hemî tiştên din ên pêwîst diyar dike. taybetmendiyên. Di heman demê de, nerehetiyek ji bo giraniya ne-hejmar dê hewce bike ku nîşanek bi jimareyek xala herikbar diyar bike (erê, ev nerehetiyek e, lê heke ew çend nîşanên weha nebin, û heke hûn nekin 'Wan jî ducarî "xetere" bikin, wê hingê dibe ku ew ne tiştek be). Ev tê wê wateyê ku di C++ de rêzikên cîrantiyê yên komeleyî yên dirêjkirî dikarin wiha werin destnîşankirin: std::nexşe , std:: vector> an jî std:: nexşe , std:: vektor, ku tê de nirxa yekem di "kilît-nirx-vektor" de dê giraniya keviya be, û dûv re navnîşên hejmarî yên taybetmendiyên wê hene.
Hêdane:
Di derbarê grafîkan û algorîtmayan de bi gelemperî:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorîtma: avakirin û analîz, çapa 2.: Trans. ji Îngilîzî - M.: Weşanxaneya Williams, 2011.
2. Harari Frank. Teoriya Grafîkê. M.: Mîr, 1973.
Rapora nivîskar di derbarê van heman vektor û rêzika hevgirtî ya cîranan de:
3. Çernûxov S.A. Vektora cîrantiyê û rêzika cîrantiyê ya hevedudanî wekî awayên temsîlkirin û hilanîna grafikan / SA Chernouhov. Vektora cîrantiyê û nexşeya cîrantiyê wekî strukturên daneyê ku grafiyek temsîl dikin // Berhevoka gotarên Konferansa Zanistî û Praktîkî ya Navneteweyî "Pirsgirêkên bicihanîna encamên pêşkeftinên nûjen û awayên çareserkirina wan" (Saratov, 14.09.2019ê Îlona 2019). - Sterlitamak: AMI, 65, r. 69-XNUMX
Çavkaniyên kêrhatî yên serhêl li ser mijarê:
4.
5.
Source: www.habr.com