Salam.
Bu qeyddə mən kompüter elmində qrafikləri saxlamaq üçün istifadə olunan əsas məlumat strukturlarını sadalamaq qərarına gəldim və mənim üçün bir növ "kristallaşan" daha bir neçə belə struktur haqqında danışacağam.
Beləliklə, başlayaq. Ancaq əvvəldən yox - məncə, biz hamımız qrafikin nə olduğunu və onların nə olduğunu artıq bilirik (yönləndirilmiş, yönləndirilməmiş, ağırlıqlı, çəkisiz, çoxlu kənarları və döngələri olan və ya olmayan).
Beləliklə, gedək. "Qrafik saxlama" üçün məlumat strukturları üçün hansı seçimlərimiz var?
1. Matris verilənlər strukturları
1.1 Qonşuluq matrisi. Qonşuluq matrisi, sətir və sütun başlıqlarının qrafikin təpələrinin nömrələrinə uyğun olduğu və a(i,j) elementlərinin hər birinin dəyəri təpələr arasında kənarların olması və ya olmaması ilə müəyyən edilən matrisdir. i və j (yönləndirilməmiş bir qrafik üçün belə bir matrisin simmetrik olacağı aydındır və ya bütün dəyərləri yalnız əsas diaqonalın üstündə saxladığımızla razılaşa bilərik). Çəkisiz qrafiklər üçün a(i,j) i-dən j-ə qədər olan kənarların sayı ilə (əgər belə kənar yoxdursa, onda a(i,j)= 0), çəkili qrafiklər üçün isə çəki ilə təyin edilə bilər. qeyd olunan kənarların (ümumi çəkisi).
1.2 İnsident matrisi. Bu halda bizim qrafikimiz də cədvəldə saxlanılır ki, burada bir qayda olaraq sətir nömrələri onun təpələrinin nömrələrinə, sütun nömrələri isə əvvəlcədən nömrələnmiş kənarlara uyğun gəlir. Əgər təpə və kənar bir-birinə düşürsə, o zaman uyğun xanaya sıfırdan fərqli qiymət yazılır (istiqamətləndirilməmiş qrafiklər üçün təpə və kənar düşərsə 1, yönümlülər üçün isə kənar olarsa “1” yazılır. təpədən “çıxır” və “daxildirsə” “-1” (xatırlamaq kifayət qədər asandır, çünki “mənfi” işarəsi də “-1” rəqəminə “daxil” kimi görünür)). Çəkili qrafiklər üçün yenə 1 və -1 əvəzinə, kənarın ümumi çəkisini təyin edə bilərsiniz.
2. Sadalama məlumat strukturları
2.1 Qonşuluq siyahısı. Bax, burada hər şey sadə görünür. Qrafikin hər bir təpəsi, ümumiyyətlə, verilmiş birinə bitişik bütün təpələrin nömrələrini saxlayacaq hər hansı bir sadalama strukturu (siyahı, vektor, massiv, ...) ilə əlaqələndirilə bilər. İstiqamətləndirilmiş qrafiklər üçün biz bu siyahıya yalnız xüsusiyyət təpəsindən “istiqamətləndirilmiş” kənarın olduğu təpələri əlavə edəcəyik. Çəkili qrafiklər üçün icra daha mürəkkəb olacaq.
2.2 Qabırğaların siyahısı. Olduqca məşhur bir məlumat strukturu. Kənarların siyahısı, Captain Obviousness-in bizə dediyi kimi, əslində qrafikin kənarlarının siyahısıdır, hər biri başlanğıc təpəsi, son zirvəsi ilə müəyyən edilir (istiqamətsiz qrafiklər üçün burada sıra vacib deyil, baxmayaraq ki, birləşmə üçün edə bilərsiniz. müxtəlif qaydalardan istifadə edin, məsələn, artan qaydada təpələri göstərin) və çəki (yalnız çəkili qrafiklər üçün).
Yuxarıda sadalanan matris siyahılarına daha ətraflı (və təsvirlərlə) baxa bilərsiniz, məsələn, .
2.3 Qonşuluq massivi. Ən ümumi quruluş deyil. Özündə bu, bitişik siyahıların bir siyahı strukturuna (massiv, vektor) “toplanması” formasıdır. Belə massivin ilk n (qrafik təpələrinin sayına görə) elementləri eyni massivin başlanğıc indekslərini ehtiva edir, ondan başlayaraq verilmiş birinə bitişik olan bütün təpələr cərgədə yazılır.
Burada ən başa düşülən (özüm üçün) izahat tapdım:
3. Qonşuluq vektoru və assosiativ qonşuluq massivi
Məlum oldu ki, bu sətirlərin müəllifi peşəkar proqramçı olmayan, lakin vaxtaşırı qrafiklərlə məşğul olan, ən çox kənarların siyahıları ilə məşğul olurdu. Həqiqətən, qrafikdə çoxlu döngələr və kənarlar varsa, rahatdır. Beləliklə, kənarların klassik siyahılarının işlənib hazırlanmasında onların “inkişafına/şaxəsinə/modifikasiyasına/mutasiyasına”, yəni bitişiklik vektoruna və assosiativ bitişiklik massivinə diqqət yetirməyi təklif edirəm.
3.1 Qonşuluq vektoru
Hal (a1): çəkilməmiş qrafik
Çəkisiz qrafik üçün bitişiklik vektorunu cüt sayda tam ədədlərdən ibarət (a[2i], a[2i+1],..., burada i c 0 ilə nömrələnir), hər bir ədəd cütü adlandıracağıq. a[2i], a[2i+1 ] müvafiq olaraq a[2i] və a[2i+1] təpələri arasında qrafik kənarını təyin edir.
Bu qeyd formatında qrafikin yönləndirilib-söndürülməməsi haqqında məlumat yoxdur (hər iki seçim mümkündür). Diqraf formatından istifadə edərkən kənarın a[2i]-dən a[2i+1]-ə istiqamətlənmiş olduğu hesab edilir. Burada və aşağıda: yönləndirilməyən qrafiklər üçün zərurət yarandıqda təpələrin qeydə alınması qaydasına dair tələblər tətbiq oluna bilər (məsələn, ona təyin edilmiş nömrənin aşağı qiyməti olan təpənin birinci olması).
C++ dilində std::vector istifadə edərək bitişiklik vektorunu təyin etmək məqsədəuyğundur, ona görə də bu verilənlər strukturunun adı.
Case (a2): çəkilməmiş qrafik, kənar çəkilər tam ədəddir
(a1) halına bənzətməklə, biz tam ədəd kənar çəkiləri olan çəkili qrafik üçün bitişiklik vektorunu sıralı ədədlər dəsti (dinamik massivi) adlandırırıq (a[3i], a[3i+1], a[3i+2], ..., burada i nömrələnmiş c 0), burada a[3i], a[3i+1], a[3i+2] ədədlərinin hər bir “üçliyi” a[3i] nömrələnmiş təpələr arasında qrafikin kənarını təyin edir. və müvafiq olaraq a[3i+1] və a [3i+2] dəyəri bu kənarın çəkisidir. Belə bir qrafik həm də yönəldilə bilər, ya da yox.
Case (b): çəkilməmiş qrafik, tam olmayan kənar çəkilər
Heterojen elementləri bir massivdə (vektorda) saxlamaq mümkün olmadığından, məsələn, aşağıdakı həyata keçirmək mümkündür. Qrafik vektor cütlüyündə saxlanılır, burada birinci vektor çəkilər göstərilmədən qrafikin bitişik vektorudur, ikinci vektor isə müvafiq çəkiləri ehtiva edir (C++: std::pair üçün mümkün tətbiqetmə) ). Beləliklə, birinci vektorun 2i, 2i+1 indeksləri altında təpələr cütü ilə müəyyən edilən kənar üçün çəki ikinci vektorun i indeksinin altındakı elementə bərabər olacaqdır.
Yaxşı, bu niyə lazımdır?
Bəli, bu sətirlərin müəllifi bunu bir sıra problemlərin həlli üçün kifayət qədər faydalı hesab etdi. Yaxşı, rəsmi nöqteyi-nəzərdən aşağıdakı üstünlüklər olacaq:
- Qonşuluq vektoru, hər hansı digər “sadalayıcı” struktur kimi, kifayət qədər yığcamdır, bitişiklik matrisindən (seyrək qrafiklər üçün) daha az yaddaş tutur və icrası nisbətən asandır.
- Qrafikin təpələri, prinsipcə, mənfi ədədlərlə də qeyd oluna bilər. Bəs belə bir “pozğunluq” lazımdırsa?
- Qrafiklər müxtəlif çəkilərlə (müsbət, mənfi, hətta sıfır) çox kənar və çoxlu döngələrdən ibarət ola bilər. Burada heç bir məhdudiyyət yoxdur.
- Siz həmçinin kənarlara müxtəlif xassələr təyin edə bilərsiniz - lakin bu barədə ətraflı məlumat üçün bölmə 4-ə baxın.
Bununla belə, etiraf etmək lazımdır ki, bu “siyahı” kənara sürətli çıxış demək deyil. Və burada aşağıda müzakirə olunan Assosiativ Qonşuluq Array köməyə gəlir.
3.2 Assosiativ bitişiklik massivi
Deməli, əgər konkret kənara, onun çəkisinə və digər xassələrinə çıxış bizim üçün kritikdirsə və yaddaş tələbləri bizə bitişiklik matrisindən istifadə etməyə imkan vermirsə, o zaman bu problemi həll etmək üçün qonşuluq vektorunu necə dəyişə biləcəyimizi düşünək. Beləliklə, açar sıralı tam ədədlər cütü kimi təyin oluna bilən qrafikin kənarıdır. Bu nə kimi görünür? Bu, assosiativ massivdə açar deyilmi? Və əgər belədirsə, niyə biz bunu həyata keçirmirik? Gəlin bizə assosiativ massiv olsun ki, burada hər bir açar - sıralı tam ədədlər cütü - bir dəyərlə - tam ədəd və ya kənarın çəkisini təyin edən real ədədlə əlaqələndiriləcək. C++ dilində bu strukturun std::map konteynerinə (std::map) əsaslanaraq həyata keçirilməsi məqsədəuyğundur. , int> və ya std::map , double>), və ya std::multimap, əgər birdən çox kənar gözlənilirsə. Yaxşı, bizdə “matris” strukturlarından daha az yaddaş tutan, çoxlu döngə və kənarları olan qrafikləri təyin edə bilən və hətta təpə nömrələrinin mənfi olmaması üçün ciddi tələbləri olmayan (bilmirəm) qrafikləri saxlamaq üçün strukturumuz var. bu kimə lazımdır, amma yenə də).
4. Məlumat strukturları doludur, lakin bir şey çatışmır
Və bu doğrudur: bir sıra problemləri həll edərkən qrafikin kənarlarına bəzi xüsusiyyətlər təyin etmək və müvafiq olaraq onları saxlamaq lazım ola bilər. Əgər bu xüsusiyyətləri birmənalı şəkildə tam ədədlərə endirmək mümkündürsə, o zaman bitişiklik vektorunun və assosiativ bitişiklik massivinin genişləndirilmiş versiyalarından istifadə etməklə belə “əlavə xüsusiyyətləri olan qrafikləri” saxlamaq mümkündür.
Beləliklə, hər bir kənarı üçün, məsələn, tam ədədlərlə göstərilən 2 əlavə xüsusiyyəti saxlamaq lazım olan çəkisiz bir qrafikimiz olsun. Bu halda onun bitişiklik vektorunu “cütlərdən” deyil, tam ədədlərdən ibarət “dördlüklərdən” (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , burada a[2i+2] və a[2i+3] müvafiq kənarın xüsusiyyətlərini təyin edəcək. Kənarların tam çəkisi olan qrafik üçün qayda ümumiyyətlə oxşardır (yeganə fərq atributların kənarın çəkisinə uyğun olması və a[2i+3] və a[2i+4] elementləri ilə təyin olunmasıdır. , və kənarın özü 4 deyil, 5 sıralı nömrə göstəriləcəkdir). Tam olmayan kənar çəkiləri olan bir qrafik üçün xüsusiyyətlər onun ölçülməmiş komponentinə yazıla bilər.
Tam kənar çəkiləri olan qrafiklər üçün assosiativ bitişiklik massivindən istifadə edərkən, qiymət kimi tək ədədi deyil, kənarın çəkisindən əlavə, onun bütün digər zəruri elementlərini təyin edən nömrələr massivini (vektorunu) göstərmək olar. xüsusiyyətləri. Eyni zamanda, tam olmayan çəkilər üçün bir narahatlıq, üzən nöqtə nömrəsi olan bir işarənin göstərilməsinə ehtiyac olacaqdır (bəli, bu bir narahatlıqdır, lakin bu cür əlamətlər çox deyilsə və əgər Onları çox "çətin" ikiqat təyin etməyin, onda heç bir şey ola bilməz). Bu o deməkdir ki, C++-da genişləndirilmiş assosiativ qonşuluq massivləri aşağıdakı kimi müəyyən edilə bilər: std::map , std::vector> və ya std::map , std::vektor, burada “açar-dəyər-vektor”dakı ilk dəyər kənarın çəkisi olacaq, sonra isə onun atributlarının ədədi təyinatları yerləşəcək.
Ədəbiyyat:
Qrafiklər və ümumiyyətlə alqoritmlər haqqında:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Alqoritmlər: tikinti və təhlil, 2-ci nəşr: Trans. ingilis dilindən – M.: Williams nəşriyyatı, 2011.
2. Harari Frank. Qrafik nəzəriyyəsi. M.: Mir, 1973.
Eyni vektor və bitişikliklərin assosiativ massivi haqqında müəllifin hesabatı:
3. Çernuxov S.A. Qonşuluq vektoru və assosiativ qonşuluq massivi qrafikləri təmsil etmək və saxlamaq yolları kimi / SA Chernouhov. Qonşuluq vektoru və bitişiklik xəritəsi qrafiki təmsil edən məlumat strukturları kimi // “İnnovativ işlənmələrin nəticələrinin tətbiqi problemləri və onların həlli yolları” Beynəlxalq Elmi-Praktik Konfransın məqalələr toplusu (Saratov, 14.09.2019 sentyabr 2019-cu il). – Sterlitamak: AMI, 65, səh. 69-XNUMX
Mövzu ilə bağlı faydalı onlayn mənbələr:
4.
5.
Mənbə: www.habr.com