Halo kabeh.
Ing cathetan iki, aku mutusaké kanggo dhaftar struktur data utama digunakake kanggo nyimpen grafik ing ilmu komputer, lan aku uga bakal pirembagan bab saperangan liyane struktur kuwi sing piye wae "crystallized" kanggo kula.
Dadi, ayo miwiti. Nanging ora saka wiwitan - aku kabeh wis ngerti apa grafik lan apa iku (diarahake, ora diarahake, bobot, ora bobot, nganggo utawa tanpa sawetara pinggiran lan puteran).
Dadi, ayo padha lunga. Apa opsi kanggo struktur data kanggo "panyimpenan grafik" kita duwe?
1. Struktur data matriks
1.1 Matriks adjacency. Matriks adjacency yaiku matriks sing judhul baris lan kolom cocog karo nomer simpul grafik, lan nilai saben unsur a(i,j) ditemtokake dening anane utawa ora ana pinggiran antarane vertex. i lan j (jelas yen kanggo grafik sing ora diarahake, matriks kasebut bakal simetris, utawa kita bisa setuju yen kita nyimpen kabeh nilai mung ing ndhuwur diagonal utama). Kanggo grafik tanpa bobot, a(i,j) bisa disetel kanthi jumlah pinggiran saka i nganti j (yen ora ana pinggiran kasebut, banjur a(i,j)= 0), lan kanggo grafik bobot, uga kanthi bobot. (bobot total) saka pinggiran kasebut.
1.2 Matriks kedadeyan. Ing kasus iki, grafik kita uga disimpen ing tabel ing ngendi, minangka aturan, nomer baris cocog karo nomer vertex sawijining, lan nomer kolom cocog karo sudhut sing wis nomer. Yen vertex lan pinggiran ana kedadeyan, banjur nilai non-nol ditulis ing sel sing cocog (kanggo grafik sing ora diarahake, 1 ditulis yen vertex lan pinggiran kedadeyan, kanggo grafik berorientasi - "1" yen pinggiran "metu" saka vertex lan "-1" yen "kalebu" ing (iku cukup gampang kanggo elinga, amarga tandha "minus" uga katon "kalebu" ing nomer "-1")). Kanggo grafik bobot, maneh, tinimbang 1 lan -1, sampeyan bisa nemtokake bobot total pinggiran.
2. Struktur data enumerasi
2.1 Dhaptar adjacency. Inggih, kabeh katon prasaja ing kene. Saben vertex saka grafik bisa, ing umum, digandhengake karo sembarang struktur enumerasi (dhaftar, vektor, array, ...), kang bakal nyimpen nomer kabeh vertex jejer kanggo siji diwenehi. Kanggo grafik sing diarahake, kita bakal nambahake dhaptar kasebut mung simpul sing ana pinggiran "diarahake" saka pucuk fitur. Kanggo grafik bobot, implementasine bakal luwih rumit.
2.2 Dhaptar iga. Struktur data sing cukup populer. Dhaptar pinggiran, kaya sing dikandhakake Kapten Obviousness, sejatine minangka dhaptar pinggiran grafik, sing saben-saben ditemtokake dening vertex wiwitan, vertex pungkasan (kanggo grafik sing ora diarahake urutane ora penting ing kene, sanajan kanggo manunggalake sampeyan bisa nggunakake macem-macem aturan, contone, nemtokake vertex supaya nambah) lan bobot (mung kanggo grafik bobot).
Sampeyan bisa ndeleng dhaptar matriks ing ndhuwur kanthi luwih rinci (lan nganggo ilustrasi), contone, .
2.3 Array Adjacency. Ora struktur sing paling umum. Ing inti, iku wangun "packing" dhaptar adjacency menyang siji struktur enumerasi (array, vektor). N pisanan (miturut jumlah vertices saka grafik) unsur Uploaded kuwi ngemot indeks wiwitan saka Uploaded padha, wiwit kang kabeh vertex jejer kanggo diwenehi ditulis ing baris.
Ing kene aku nemokake panjelasan sing paling bisa dingerteni (kanggo aku):
3. Vektor Adjacency lan Array Adjacency Asosiatif
Ternyata penulis garis kasebut, ora dadi programer profesional, nanging sing sacara periodik ngurusi grafik, paling kerep ngurusi dhaptar pinggiran. Pancen, trep yen grafik duwe pirang-pirang puteran lan pinggir. Dadi, ing pangembangan dhaptar klasik pinggiran, aku ngusulake kanggo menehi perhatian marang "pembangunan / cabang / modifikasi / mutasi", yaiku: vektor adjacency lan array adjacency associative.
3.1 Vektor adjacency
Kasus (a1): grafik tanpa bobot
Kita bakal nyebut vektor adjacency kanggo graph tanpa bobot minangka himpunan urut saka wilangan wilangan genap (a[2i], a[2i+1],..., ing ngendi i diwenehi nomer c 0), sing saben pasangan nomer. yaiku a[2i], a[2i+1 ] nemtokake pinggiran grafik antarane vertex a[2i] lan a[2i+1], mungguh.
Format rekaman iki ora ngemot informasi babagan apa grafik diarahake (loro pilihan bisa). Nalika nggunakake format digraph, pinggiran dianggep diarahake saka a[2i] menyang a[2i+1]. Ing kene lan ing ngisor iki: kanggo grafik sing ora diarahake, yen perlu, syarat kanggo urutan rekaman simpul bisa diterapake (contone, vertex kanthi angka sing luwih murah saka nomer sing ditugasake luwih dhisik).
Ing C ++, disaranake kanggo nemtokake vektor adjacency nggunakake std :: vektor, mula jeneng struktur data iki.
Kasus (a2): grafik tanpa bobot, bobot pinggir minangka integer
Kanthi analogi karo kasus (a1), kita nyebut vektor adjacency kanggo grafik bobot kanthi bobot pinggiran integer minangka set terurut (array dinamis) nomer (a[3i], a[3i+1], a[3i+2], ..., ing ngendi i diwenehi nomer c 0), ing ngendi saben "triplet" saka nomer a[3i], a[3i+1], a[3i+2] nemtokake pinggiran grafik ing antarane vertex kanthi nomer a[3i] lan a[3i+1], lan nilai a [3i+2] minangka bobot pinggiran iki. Grafik kasebut uga bisa diarahake utawa ora.
Kasus (b): grafik tanpa bobot, bobot pinggiran non-integer
Amarga ora bisa nyimpen unsur heterogen ing siji array (vektor), contone, implementasine ing ngisor iki bisa ditindakake. Grafik disimpen ing pasangan vektor, ing ngendi vektor pisanan minangka vektor adjacency grafik tanpa nemtokake bobot, lan vektor kapindho ngemot bobot sing cocog (bisa implementasine kanggo C++: std:: pasangan ). Dadi, kanggo pinggiran sing ditetepake dening pasangan vertex ing indeks 2i, 2i + 1 saka vektor pisanan, bobote bakal padha karo unsur ing indeks i saka vektor kaloro.
Lha, kenapa iki perlu?
Inggih, penulis garis iki ketemu cukup migunani kanggo ngrampungake sawetara masalah. Inggih, saka sudut pandang formal, bakal ana kaluwihan ing ngisor iki:
- Vektor adjacency, kaya struktur "enumeratif" liyane, cukup kompak, njupuk memori kurang saka matriks adjacency (kanggo grafik jarang), lan relatif gampang kanggo ngleksanakake.
- Pucuk grafik, ing prinsip, bisa uga ditandhani karo angka negatif. Apa yen "perversion" kuwi dibutuhake?
- Grafik bisa ngemot pirang-pirang pinggiran lan pirang-pirang puteran, kanthi bobot sing beda (positif, negatif, malah nol). Ora ana watesan ing kene.
- Sampeyan uga bisa nemtokake properti sing beda-beda menyang pinggir - nanging kanggo luwih lengkap, deleng bagean 4.
Nanging, kudu diakoni yen "dhaptar" iki ora ateges akses cepet menyang pinggir. Lan ing kene Associative Adjacency Array teka kanggo ngluwari, sing dibahas ing ngisor iki.
3.2 Array adjacency asosiatif
Dadi, yen akses menyang pinggiran tartamtu, bobot lan sifat liyane kritis kanggo kita, lan syarat memori ora ngidini kita nggunakake matriks adjacency, banjur ayo kang mikir bab carane ngganti vektor adjacency kanggo ngatasi masalah iki. Dadi, kunci kasebut minangka pinggiran grafik, sing bisa ditemtokake minangka pasangan integer sing diurutake. Kaya apa iki? Apa ora dadi kunci ing array asosiatif? Lan, yen mangkono, kenapa kita ora ngetrapake? Ayo kita duwe array asosiatif ing ngendi saben tombol - pasangan integer sing diurutake - bakal digandhengake karo nilai - integer utawa nomer nyata sing nemtokake bobot pinggiran. Ing C ++, disaranake kanggo ngetrapake struktur iki adhedhasar std :: map container (std :: map , int> utawa std::map , pindho>), utawa std::multimap yen sawetara sudhut samesthine. Inggih, kita duwe struktur kanggo nyimpen grafik sing njupuk munggah memori kurang saka struktur "matriks", bisa nemtokake grafik karo macem-macem puteran lan sudhut, lan malah ora duwe syarat ketat kanggo non-negativitas nomer vertex (Aku ora ngerti. sing mbutuhake iki, nanging isih).
4. Struktur data kebak, nanging ana sing ilang
Lan bener: nalika ngrampungake sawetara masalah, kita bisa uga kudu nemtokake sawetara karakteristik ing pinggir grafik lan, kanthi mangkono, nyimpen. Yen sampeyan bisa nyuda fitur-fitur kasebut dadi wilangan bulat, mula bisa nyimpen "grafik kanthi fitur tambahan" kanthi nggunakake versi lengkap vektor adjacency lan array adjacency asosiatif.
Dadi, ayo duwe grafik sing ora bobot, kanggo saben pinggiran sing kudu disimpen, contone, 2 fitur tambahan sing ditemtokake dening wilangan bulat. Ing kasus iki, bisa ditetepake vektor adjacency minangka himpunan urutan ora saka "pasangan", nanging saka "kuartets" integers (a[2i], a[2i+1], a[2i+2], a [2i+3]…), ing ngendi a[2i+2] lan a[2i+3] bakal nemtokake karakteristik pinggiran sing cocog. Kanggo grafik kanthi bobot integer pinggiran, urutane umume padha (mung bedane yaiku kasunyatan yen atribut bakal ngetutake bobot pinggiran lan bakal ditemtokake dening unsur a[2i+3] lan a[2i+ 4], lan pinggiran dhewe bakal kasebut ora 4, nanging 5 nomer dhawuh). Lan kanggo grafik kanthi bobot pinggiran non-integer, fitur kasebut bisa ditulis ing komponen tanpa bobot.
Nalika nggunakake array adjacency associative kanggo grafik kanthi bobot pinggiran integer, sampeyan bisa nemtokake minangka nilai dudu nomer siji, nanging array (vektor) nomer sing nemtokake, saliyane bobot pinggiran, kabeh sing perlu. fitur. Ing wektu sing padha, ora nyaman kanggo kasus bobot non-integer kudu nemtokake tandha kanthi nomer floating point (ya, iki ora nyenengake, nanging yen ora ana akeh pratandha, lan yen sampeyan 't nyetel wong-wong mau banget "angel" pindho, banjur bisa apa-apa). Iki tegese ing C ++, array adjacency asosiatif lengkap bisa ditetepake kaya ing ngisor iki: std :: map , std::vector> utawa std::map , std :: vektor, ing ngendi nilai pisanan ing "key-value-vector" bakal dadi bobot pinggiran, lan banjur ana sebutan numerik saka atribut kasebut.
Sastra:
Babagan grafik lan algoritma umume:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritma: konstruksi lan analisis, 2nd edition: Trans. saka Inggris – M.: Williams Publishing House, 2011.
2. Harari Frank. Teori grafik. M.: Mir, 1973.
Laporan penulis babagan vektor sing padha lan array asosiatif saka adjacencies:
3. Chernoukhov S.A. Vektor adjacency lan array adjacency asosiatif minangka cara kanggo makili lan nyimpen grafik / SA Chernouhov. Vektor adjacency lan peta adjacency minangka struktur data kanggo makili grafik // Koleksi artikel Konferensi Ilmiah lan Praktis Internasional "Masalah ngleksanakake asil pangembangan inovatif lan cara kanggo ngatasi" (Saratov, 14.09.2019 September 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
Sumber online sing migunani babagan topik:
4.
5.
Source: www.habr.com