Nyob zoo txhua tus.
Hauv daim ntawv no, kuv tau txiav txim siab sau cov ntaub ntawv tseem ceeb uas siv los khaws cov duab hauv computer science, thiab kuv tseem yuav tham txog ob peb yam ntxiv uas "crystallized" rau kuv.
Yog li, cia peb pib. Tab sis tsis yog los ntawm qhov pib - Kuv xav tias peb txhua tus twb paub tias daim duab yog dab tsi thiab lawv yog dab tsi (qhia, tsis qhia, hnyav, tsis hnyav, nrog lossis tsis muaj ntau lub npoo thiab voj).
Yog li, cia peb mus. Cov kev xaiv twg rau cov qauv ntaub ntawv rau "graph storage" peb puas muaj?
1. Matrix cov ntaub ntawv qauv
1.1 Adjacency matrix. Lub adjacency matrix yog ib tug matrix qhov twg kab thiab kab ntawv kab lus sib haum mus rau cov zauv ntawm lub vertices ntawm daim duab, thiab tus nqi ntawm txhua yam ntawm nws cov ntsiab a(i,j) yog txiav txim los ntawm lub xub ntiag los yog tsis muaj ntug ntawm vertices. i thiab j (nws yog tseeb hais tias rau ib tug undirected graph xws li ib tug matrix yuav symmetrical, los yog peb yuav pom zoo tias peb khaws tag nrho cov nqi tsuas yog saum toj no lub ntsiab kab pheeb ces kaum). Rau cov duab tsis hnyav, a(i,j) tuaj yeem tsim los ntawm cov npoo ntawm i mus rau j (yog tias tsis muaj ntug, ces a(i,j) = 0), thiab rau cov duab hnyav, kuj los ntawm qhov hnyav. (tag nrho qhov hnyav) ntawm cov npoo hais.
1.2 Qhov xwm txheej matrix. Hauv qhov no, peb daim duab tseem khaws cia rau hauv ib lub rooj uas, raws li txoj cai, cov kab zauv sib raug rau cov lej ntawm nws cov vertices, thiab cov kab zauv sib raug rau cov lej ua ntej. Yog hais tias lub vertex thiab ntug yog qhov teeb meem rau ib leeg, ces tus nqi tsis yog xoom yog sau rau hauv cov khoom sib txuas (rau cov duab tsis qhia, 1 yog sau yog tias lub vertex thiab ntug yog qhov xwm txheej, rau cov duab taw qhia - "1" yog tias ntug "tawm" los ntawm lub vertex thiab "-1" yog tias nws "suav nrog" hauv nws (nws yooj yim txaus los nco ntsoov, vim hais tias cov cim "tshem tawm" kuj zoo li "suav nrog" hauv tus lej "-1")). Rau cov duab hnyav, dua, tsis yog 1 thiab -1, koj tuaj yeem qhia tag nrho qhov hnyav ntawm ntug.
2. Cov ntaub ntawv suav sau
2.1 Daim ntawv teev npe. Zoo, txhua yam zoo li yooj yim ntawm no. Txhua qhov vertex ntawm daim duab tuaj yeem, feem ntau, cuam tshuam nrog txhua tus qauv sau npe (daim ntawv, vector, array, ...), uas yuav khaws cov lej ntawm tag nrho cov vertices nyob ib sab ntawm qhov muab. Rau cov duab qhia, peb yuav ntxiv rau cov npe zoo li no tsuas yog cov vertices uas muaj "qhia" ntug ntawm ib qho vertex. Rau qhov hnyav graphs qhov kev siv yuav nyuaj dua.
2.2 Daim ntawv teev cov tav. Heev ib tug nrov cov ntaub ntawv qauv. Daim ntawv teev cov npoo, raws li tus tauj ncov loj Obviousness qhia peb, yog ib daim ntawv teev cov npoo ntawm daim duab, txhua tus uas tau teev tseg los ntawm qhov pib vertex, qhov kawg vertex (rau undirected graphs qhov kev txiav txim tsis tseem ceeb ntawm no, tab sis rau kev sib koom ua ke koj tuaj yeem ua tau. siv ntau yam kev cai, piv txwv li, qhia cov vertices nyob rau hauv thiaj li yuav nce) thiab hnyav (rau qhov hnyav graphs nkaus xwb).
Koj tuaj yeem saib cov npe matrix uas tau teev tseg saum toj no hauv kev nthuav dav ntxiv (thiab nrog cov duab kos), piv txwv li, .
2.3 Adjacency array. Tsis yog cov qauv feem ntau. Ntawm nws cov tub ntxhais, nws yog ib daim ntawv ntawm "packing" adjacency cov npe rau hauv ib qho qauv sau npe (array, vector). Thawj n (raws li tus naj npawb ntawm vertices ntawm daim duab) cov ntsiab lus ntawm xws li ib qho array muaj qhov pib indices ntawm tib array, pib los ntawm tag nrho cov vertices uas nyob ib sab mus rau ib tug muab sau ua ke.
Ntawm no kuv pom qhov nkag siab tshaj plaws (rau kuv tus kheej) piav qhia:
3. Adjacency Vector thiab Associative Adjacency Array
Nws muab tawm tias tus sau ntawm cov kab no, tsis yog tus kws tshaj lij programmer, tab sis leej twg ua haujlwm nrog cov duab kos, feem ntau cuam tshuam nrog cov npe ntawm cov npoo. Tseeb, nws yog qhov yooj yim yog tias daim duab muaj ntau lub voj voog thiab cov npoo. Thiab yog li ntawd, hauv kev txhim kho cov npe ntawm cov npoo, kuv xav kom them sai sai rau lawv cov "kev loj hlob / ceg / kev hloov kho / kev hloov", uas yog: lub adjacency vector thiab associative adjacency array.
3.1 Adjacency vector
Case (a1): cov duab tsis hnyav
Peb yuav hu rau ib tug adjacency vector rau ib tug unweighted graph ib tug txiav txim ntawm ib tug txawm tus naj npawb ntawm integers (a[2i], a[2i + 1], ..., qhov twg kuv yog suav c 0), nyob rau hauv uas txhua khub ntawm cov zauv yog a[2i], a[2i+1] qhia ib daim duab ntug ntawm cov vertices a[2i] thiab a[2i+1], feem.
Hom ntawv kaw no tsis muaj cov ntaub ntawv hais txog seb daim duab qhia tau li cas (ob qho tib si muaj peev xwm ua tau). Thaum siv cov qauv digraph, ntug tau txiav txim siab los ntawm a[2i] mus rau [2i+1]. Ntawm no thiab hauv qab no: rau cov duab tsis ncaj ncees, yog tias tsim nyog, yuav tsum tau ua rau kev txiav txim ntawm kev kaw cov vertices tuaj yeem siv tau (piv txwv li, qhov vertex nrog tus nqi qis ntawm tus lej muab rau nws los ua ntej).
Hauv C ++, nws raug nquahu kom hais kom meej ib qho adjacency vector siv std:: vector, li no lub npe ntawm cov ntaub ntawv qauv.
Case (a2): cov duab tsis hnyav, ntug qhov hnyav yog tus lej
Los ntawm kev sib piv nrog cov ntaub ntawv (a1), peb hu rau qhov adjacency vector rau ib daim duab hnyav nrog cov lej ntawm qhov hnyav ib qho kev txiav txim (dynamic array) ntawm cov lej (a[3i], a[3i+1], a[3i+2], ..., qhov twg kuv yog tus lej c 0), qhov twg txhua "triplet" ntawm tus lej a[3i], a[3i + 1], a[3i + 2] qhia txog ntug ntawm daim duab ntawm vertices suav a[3i] thiab a[3i+1], ntsig txog, thiab tus nqi a [3i+2] yog qhov hnyav ntawm ntug no. Xws li ib daim duab kuj tuaj yeem coj los yog tsis tau.
Case (b): cov duab tsis hnyav, tsis yog tus lej ntawm ntug qhov hnyav
Txij li thaum nws tsis tuaj yeem khaws cov ntsiab lus heterogeneous hauv ib qho array (vector), piv txwv li, kev siv hauv qab no yog ua tau. Daim duab muab khaws cia rau hauv ib khub ntawm vectors, uas thawj vector yog daim duab adjacency vector yam tsis tau qhia qhov hnyav, thiab qhov thib ob vector muaj qhov hnyav sib xws (muaj peev xwm siv tau rau C ++: std::pair ). Yog li, rau ib tug ntug txhais los ntawm ib khub ntawm vertices nyob rau hauv indexes 2i, 2i + 1 ntawm thawj vector, qhov hnyav yuav sib npaug rau lub caij nyob rau hauv index i ntawm lub thib ob vector.
Zoo, vim li cas qhov no tsim nyog?
Zoo, tus sau ntawm cov kab no pom tias nws muaj txiaj ntsig zoo rau kev daws teeb meem ntau yam. Zoo, los ntawm kev pom zoo, yuav muaj qhov zoo hauv qab no:
- Lub adjacency vector, zoo li lwm yam "numerative" qauv, yog qhov sib txuam, siv lub cim xeeb tsawg dua li qhov adjacency matrix (rau cov duab sib luag), thiab yooj yim rau kev siv.
- Lub vertices ntawm daim duab, hauv paus ntsiab lus, kuj tuaj yeem raug cim nrog tus lej tsis zoo. Yuav ua li cas yog tias qhov "perversion" xav tau?
- Cov kab kos tuaj yeem muaj ntau cov npoo thiab ntau lub voj voog, nrog qhov hnyav sib txawv (zoo, tsis zoo, txawm xoom). Tsis muaj kev txwv ntawm no.
- Koj tuaj yeem muab cov khoom sib txawv rau cov npoo - tab sis xav paub ntxiv txog qhov ntawd, saib nqe 4.
Txawm li cas los xij, nws yuav tsum tau lees paub tias qhov "daim ntawv teev npe" no tsis txhais tau tias nkag mus sai rau ntawm ntug. Thiab ntawm no Associative Adjacency Array los cawm, uas tau tham hauv qab no.
3.2 Associative adjacency array
Yog li, yog tias nkag mus rau ib qho ntug tshwj xeeb, nws qhov hnyav thiab lwm yam khoom tseem ceeb rau peb, thiab cov kev xav nco tsis tso cai rau peb siv cov adjacency matrix, ces cia peb xav txog yuav ua li cas peb tuaj yeem hloov qhov adjacency vector los daws qhov teeb meem no. Yog li, tus yuam sij yog ib qho ntug ntawm daim duab, uas tuaj yeem teev tau raws li kev txiav txim ntawm tus lej. Qhov no zoo li cas? Nws tsis yog qhov tseem ceeb hauv kev sib koom ua ke? Thiab, yog tias muaj, vim li cas peb tsis ua nws? Cia peb muaj ib qho associative array qhov twg txhua tus yuam sij - ib khub ntawm cov lej - yuav raug cuam tshuam nrog tus nqi - tus lej lossis tus lej tiag uas qhia qhov hnyav ntawm ntug. Hauv C ++, nws raug nquahu kom siv cov qauv no raws li std:: map container (std::map , int> or std::map , double>), los yog std::multimap yog tias xav tau ntau cov npoo. Zoo, peb muaj cov qauv rau kev khaws cov duab uas siv lub cim xeeb tsawg dua li "matrix" cov qauv, tuaj yeem txhais cov duab nrog ntau lub voj voog thiab cov npoo, thiab tsis txawm tias muaj cov cai nruj rau qhov tsis zoo ntawm cov lej vertex (Kuv tsis paub. leej twg xav tau qhov no, tab sis tseem).
4. Cov qauv ntaub ntawv yog tag nrho, tab sis ib yam dab tsi ploj lawm
Thiab nws muaj tseeb: thaum daws tau ntau yam teeb meem, peb yuav tsum tau muab qee tus yam ntxwv rau cov npoo ntawm daim duab thiab, raws li, khaws cia. Yog tias nws muaj peev xwm txo qis cov yam ntxwv no rau cov lej, ces nws tuaj yeem khaws cov "graphs nrog cov yam ntxwv ntxiv" siv cov ntawv txuas ntxiv ntawm qhov adjacency vector thiab associative adjacency array.
Yog li, cia peb muaj cov duab tsis hnyav, rau txhua qhov ntug uas nws yuav tsum tau khaws cia, piv txwv li, 2 ntxiv nta tau teev los ntawm cov lej. Hauv qhov no, nws tuaj yeem txhais nws qhov chaw nyob ib puag ncig raws li kev txiav txim tsis yog "pairs", tab sis ntawm "quartets" ntawm cov lej (a[2i], a[2i + 1], a [2i + 2], a [2i+3]…), qhov twg a[2i+2] thiab a[2i+3] yuav txiav txim siab cov yam ntxwv ntawm cov ntug sib thooj. Rau ib daim duab nrog qhov hnyav ntawm cov npoo, qhov kev txiav txim feem ntau zoo sib xws (qhov sib txawv tsuas yog tias cov cwj pwm yuav ua raws li qhov hnyav ntawm ntug thiab yuav tau teev los ntawm cov ntsiab lus a[2i + 3] thiab a [2i + 4] , thiab ntug nws tus kheej yuav raug teev tsis yog 4, tab sis 5 tus lej xaj). Thiab rau daim duab uas tsis yog tus lej ntawm qhov hnyav, cov yam ntxwv tuaj yeem sau rau hauv nws qhov tsis muaj qhov hnyav.
Thaum siv cov associative adjacency array rau graphs nrog cov lej ntawm qhov hnyav, nws muaj peev xwm qhia tau tias tus nqi tsis yog ib tus lej, tab sis ib qho array (vector) ntawm cov lej uas qhia, ntxiv rau qhov hnyav ntawm ntug, tag nrho nws lwm yam tsim nyog. nta. Nyob rau tib lub sijhawm, qhov tsis yooj yim rau rooj plaub uas tsis yog tus lej hnyav yuav yog qhov yuav tsum tau qhia lub cim nrog tus lej taw tes (yog, qhov no yog qhov tsis yooj yim, tab sis yog tias tsis muaj ntau cov cim, thiab yog tias koj tsis ua. 't teeb lawv dhau "nyuaj" ob, ces nws yuav tsis muaj dab tsi). Qhov no txhais tau hais tias nyob rau hauv C ++ txuas ntxiv associative adjacency arrays tuaj yeem txhais raws li hauv qab no: std::map , std::vector> los yog std::map , std::vector, uas thawj tus nqi hauv "tus nqi tseem ceeb-vector" yuav yog qhov hnyav ntawm ntug, thiab tom qab ntawd cov naj npawb ntawm nws cov yam ntxwv nyob.
Cov ntawv nyeem:
Hais txog graphs thiab algorithms feem ntau:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithms: kev tsim kho thiab kev tsom xam, 2nd tsab: Trans. los ntawm lus Askiv – M.: Williams Publishing House, 2011.
2. Harari Frank. Graph txoj kev xav. M.: Mus, 1973.
Tus sau tsab ntawv ceeb toom txog tib lub vector thiab associative array ntawm adjacencies:
3. Chernoukhov S.A. Adjacency vector thiab associative adjacency array raws li txoj hauv kev los sawv cev thiab khaws cov duab / SA Chernouhov. Adjacency vector and adjacency map as data structures to sawv cev ib daim duab // Sau cov khoom ntawm International Scientific thiab Practical Conference "Cov teeb meem ntawm kev siv cov txiaj ntsig ntawm kev tsim kho tshiab thiab txoj hauv kev los daws lawv" (Saratov, Cuaj Hlis 14.09.2019, 2019). - Sterlitamak: AMI, 65, p. 69-XNUMX : kuv
Cov peev txheej hauv online ntawm lub ncauj lus:
4.
5.
Tau qhov twg los: www.hab.com