Bonjou tout moun.
Nan nòt sa a, mwen deside lis estrikti prensipal done yo itilize pou estoke graf nan syans enfòmatik, epi mwen pral pale tou sou yon koup plis estrikti sa yo ki yon jan kanmenm "kristalize" pou mwen.
Se konsa, ann kòmanse. Men, pa depi nan konmansman an anpil - mwen panse ke nou tout deja konnen ki sa yon graf se ak sa yo ye (dirije, san direksyon, filaplon, unweighted, avèk oswa san plizyè kwen ak bouk).
Donk, ann ale. Ki opsyon pou estrikti done pou "depo graf" nou genyen?
1. Matrice done estrikti
1.1 Matris adjasans. Matris adjasans la se yon matris kote ranje ak tit kolòn yo koresponn ak nimewo somè graf la, epi valè chak eleman li yo a(i,j) detèmine pa prezans oswa absans bor ant somè yo. i ak j (li klè ke pou yon graf san direksyon tankou yon matris pral simetrik, oswa nou ka dakò ke nou estoke tout valè sèlman pi wo a dyagonal prensipal la). Pou graf ki pa pondéré, a(i,j) ka tabli pa kantite bor ki soti nan i rive nan j (si pa gen okenn kwen konsa, lè sa a a(i,j)= 0), epi pou graf pondéré, tou pa pwa. (pwa total) nan kwen yo mansyone.
1.2 Matris ensidans. Nan ka sa a, graf nou an estoke tou nan yon tablo kote, an jeneral, nimewo ranje yo koresponn ak nimewo somè li yo, epi nimewo kolòn yo koresponn ak bor pre-nimero yo. Si yon somè ak yon kwen ensidan youn ak lòt, Lè sa a, yon valè ki pa zewo ekri nan selil ki koresponn lan (pou graf san direksyon, 1 ekri si somè a ak kwen se ensidan, pou moun ki oryante - "1" si kwen an. "sòti" nan somè a ak "-1" si li "enkli" ladan l (li ase fasil pou w sonje, paske siy "mwens" la tou sanble ap "enkli" nan nimewo "-1"). Pou graf filaplon, ankò, olye pou yo 1 ak -1, ou ka presize pwa total kwen an.
2. Enumération done estrikti
2.1 Lis adjasans. Oke, tout bagay sanble senp isit la. Chak somè nan graf la ka, an jeneral, asosye ak nenpòt estrikti enimerasyon (lis, vektè, etalaj, ...), ki pral estoke nimewo yo nan tout somè adjasan ak youn nan bay la. Pou graf dirije, nou pral ajoute nan yon lis sa yo sèlman somè ki gen yon kwen "dirije" soti nan yon somè karakteristik. Pou graf pondéré, aplikasyon an pral pi konplèks.
2.2 Lis zo kòt. Byen yon estrikti done popilè. Lis bor yo, jan Kapitèn Obviousness di nou, se aktyèlman yon lis bor nan graf la, chak nan yo ki espesifye pa somè a kòmanse, somè a fini (pou graf ki pa dirije lòd la pa enpòtan isit la, byenke pou inifikasyon ou kapab itilize divès règ, pa egzanp, espesifye somè yo nan lòd ogmante) ak pwa (pou graf pondéré sèlman).
Ou ka gade nan lis matris ki nan lis pi wo a an plis detay (ak ak ilistrasyon), pou egzanp, .
2.3 Etalaj adjasans. Pa estrikti ki pi komen. Nan nwayo li yo, li se yon fòm "anbalaj" lis adjasans nan yon estrikti enimerasyon (etalaj, vektè). Premye n (dapre kantite somè nan graf la) eleman nan yon etalaj sa a gen endis yo kòmanse nan menm etalaj la, kòmanse nan ki tout somè adjasan ak youn nan yo ekri nan yon ranje.
Isit la mwen jwenn eksplikasyon ki pi konprann (pou tèt mwen):
3. Vektè Adjasans ak Etalaj Adjasans Asosyasyon
Li te tounen soti ke otè a nan liy sa yo, pa yon pwogramè pwofesyonèl, men ki detanzantan te fè fas ak graf, pi souvan te fè fas ak lis bor. Vreman vre, li bon si graf la gen plizyè bouk ak bor. Se konsa, nan devlopman nan lis yo klasik nan kwen, mwen pwopoze yo peye atansyon sou yo "devlopman / branch / modifikasyon / mitasyon", sètadi: vektè a adjasans ak etalaj la adjasans asosyasyon.
3.1 Vektè adjasans
Ka (a1): graf unweighted
Nou pral rele yon vektè adjasans pou yon graf ki pa pondéré yon seri òdone yon nonm nonm antye (a[2i], a[2i+1],..., kote i gen nimewote c 0), kote chak pè nonb. se a[2i], a[2i+1 ] espesifye yon kwen graf ant somè a[2i] ak a[2i+1], respektivman.
Fòma anrejistreman sa a pa genyen enfòmasyon sou si graf la dirije (tou de opsyon yo posib). Lè w ap itilize fòma digraf la, yo konsidere kwen an dwe dirije soti nan a[2i] rive nan a[2i+1]. Isit la ak anba a: pou graf san direksyon, si sa nesesè, kondisyon pou lòd la nan somè anrejistreman yo ka aplike (pa egzanp, somè a ki gen valè ki pi ba nan nimewo yo asiyen li a vini an premye).
Nan C++, li rekòmande pou presize yon vektè adjasans lè l sèvi avèk std::vector, kidonk non estrikti done sa a.
Ka (a2): graf san pondere, pwa kwen yo se nonb antye relatif
Pa analoji ak ka (a1), nou rele vektè adjasans pou yon graf pondéré ak pwa kwen nonb antye relatif yon seri òdone (etalaj dinamik) nimewo (a[3i], a[3i+1], a[3i+2], ..., kote i resansman c 0), kote chak “triple” nonb a[3i], a[3i+1], a[3i+2] presize yon kwen graf ant somè ki rele a[3i] ak a[3i+1], respektivman, ak valè a [3i+2] se pwa kwen sa a. Yon graf konsa kapab tou swa dirije oswa ou pa.
Ka (b): graf san pondere, pwa kwen ki pa nonb antye relatif
Depi li enposib pou estoke eleman etewojèn nan yon sèl etalaj (vektè), pou egzanp, aplikasyon sa a posib. Grafik la estoke nan yon pè vektè, kote premye vektè a se vektè adjasans graf la san yo pa espesifye pwa yo, epi dezyèm vektè a gen pwa ki koresponn yo (enplikasyon posib pou C++: std::pair). ). Kidonk, pou yon kwen defini pa yon pè somè anba endèks 2i, 2i+1 nan premye vektè a, pwa a pral egal ak eleman ki anba endèks i nan dezyèm vektè a.
Oke, poukisa sa nesesè?
Oke, otè a nan liy sa yo te jwenn li byen itil pou rezoud yon kantite pwoblèm. Oke, nan yon pwen de vi fòmèl, pral gen avantaj sa yo:
- Vektè adjasans la, tankou nenpòt lòt estrikti "enumeratif", byen kontra enfòmèl ant, li pran mwens memwa pase matris adjasans lan (pou graf ki ra), epi li relativman fasil pou aplike.
- Somè graf la, nan prensip, kapab tou make ak nimewo negatif. E si yo bezwen yon "pervèsyon" konsa?
- Graf yo ka genyen plizyè kwen ak plizyè bouk, ak pwa diferan (pozitif, negatif, menm zewo). Pa gen okenn restriksyon isit la.
- Ou kapab tou bay diferan pwopriyete nan kwen - men pou plis sou sa, gade seksyon 4.
Sepandan, li dwe admèt ke "lis" sa a pa vle di aksè rapid nan kwen an. Ak isit la Associative Adjacency Array la vini nan sekou a, ki se diskite anba a.
3.2 Etalaj adjasans asosyasyon
Se konsa, si aksè a yon kwen espesifik, pwa li yo ak lòt pwopriyete enpòtan pou nou, ak kondisyon memwa pa pèmèt nou sèvi ak matris la adjasans, Lè sa a, ann reflechi sou ki jan nou ka chanje vektè adjasans nan rezoud pwoblèm sa a. Se konsa, kle a se yon kwen nan graf la, ki ka espesifye kòm yon pè òdone nan nonm antye. Ki jan sa sanble? Èske se pa yon kle nan yon etalaj asosyasyon? Epi, si se konsa, poukisa nou pa aplike li? Se pou nou gen yon etalaj asosyasyon kote chak kle - yon pè òdone nan nonm antye - yo pral asosye ak yon valè - yon nonb antye relatif oswa yon nimewo reyèl ki presize pwa nan kwen an. Nan C++, li rekòmande pou aplike estrikti sa a ki baze sou veso std::map la (std::map , int> oswa std::map , double>), oswa std::multimap si yo espere plizyè kwen. Oke, nou gen yon estrikti pou estoke graf ki pran mwens memwa pase estrikti "matris", ki ka defini graf ki gen plizyè bouk ak bor, epi ki pa menm gen kondisyon strik pou non-negativite nan nimewo somè (mwen pa konnen ki moun ki bezwen sa a, men toujou).
4. Estrikti done yo plen, men gen yon bagay ki manke
Epi se vre: lè nou rezoud yon kantite pwoblèm, nou ka bezwen asiyen kèk karakteristik nan bor yo nan graf la epi, kòmsadwa, estoke yo. Si li posib pou redwi karakteristik sa yo san anbigwite nan nonm antye, Lè sa a, li posib pou estoke "graf ak karakteristik adisyonèl" sa yo lè l sèvi avèk vèsyon pwolonje vektè adjasans ak etalaj adjasans asosyal.
Se konsa, se pou nou gen yon graf unweighted, pou chak kwen nan ki li nesesè nan magazen, pou egzanp, 2 karakteristik adisyonèl espesifye pa nonm antye. Nan ka sa a, li posib pou defini vektè adjasans li kòm yon seri òdone pa "pè", men "quartets" nan nonm antye (a[2i], a[2i+1], a[2i+2], a. [2i+3]…) , kote a[2i+2] ak a[2i+3] ap detèmine karakteristik kwen korespondan an. Pou yon graf ki gen pwa nonb antye relatif nan kwen, lòd la se jeneralman menm jan an (sèl diferans lan pral ke atribi yo pral swiv pwa nan kwen an epi yo pral espesifye pa eleman yo a[2i+3] ak a[2i+4] , ak kwen nan tèt li yo pral espesifye pa 4, men 5 nimewo òdone). Ak pou yon graf ak pwa kwen ki pa nonb antye relatif, karakteristik yo ka ekri nan eleman ki pa pondéré li yo.
Lè w ap itilize yon etalaj adjasans asosyatif pou graf ki gen pwa kwen nonb antye relatif, li posib pou presize kòm yon valè pa yon sèl nimewo, men yon etalaj (vektè) nan nimewo ki presize, anplis pwa yon kwen, tout lòt li nesesè. karakteristik. An menm tan an, yon deranjman pou ka pwa ki pa nonb antye yo pral bezwen espesifye yon siy ki gen yon nimewo pwen k ap flote (wi, sa a se yon deranjman, men si pa gen anpil siy sa yo, epi si ou don pa mete yo twò "difisil" doub, Lè sa a, li ka pa gen anyen). Sa vle di ke nan C++ pwolonje asosyasyon adjasans etalaj ka defini jan sa a: std::map , std::vector> oswa std::map , std::vector, nan ki premye valè nan "kle-valè-vektè" a pral pwa nan kwen an, ak Lè sa a, deziyasyon nimerik yo nan karakteristik li yo.
Литература:
Konsènan graf ak algoritm an jeneral:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritm: konstriksyon ak analiz, 2yèm edisyon: Trad. soti nan angle – M.: Williams Publishing House, 2011.
2. Harari Frank. Teyori graf. M.: Mir, 1973.
Rapò otè a sou menm vektè ak seri asosyasyon adjasans sa yo:
3. Chernoukhov S.A. Vektè adjasans ak etalaj adjasans asosyativ kòm fason pou reprezante ak magazen graf / SA Chernouhov. Vektè adjasans ak kat jeyografik adjasans kòm estrikti done yo reprezante yon graf // Koleksyon atik nan Konferans Entènasyonal Syantifik ak Pratik "Pwoblèm nan aplikasyon rezilta yo nan devlopman inovatè ak fason yo rezoud yo" (Saratov, 14.09.2019 septanm 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Sous itil sou entènèt sou sijè a:
4.
5.
Sous: www.habr.com