მონაცემთა სტრუქტურები გრაფიკების შესანახად: არსებული და ორი „თითქმის ახალი“ მიმოხილვა

გაუმარჯოს ყველას.

ამ ჩანაწერში გადავწყვიტე ჩამოვთვალო ძირითადი მონაცემთა სტრუქტურები, რომლებიც გამოიყენება კომპიუტერულ მეცნიერებაში გრაფიკების შესანახად და ასევე ვისაუბრებ კიდევ რამდენიმე ასეთ სტრუქტურაზე, რომლებიც რატომღაც „დაკრისტალიზებულა“ ჩემთვის.

მაშ ასე, დავიწყოთ. ოღონდ არა თავიდანვე - ვფიქრობ, ყველამ უკვე ვიცით რა არის და რა არის გრაფიკი (მიმართული, არამიმართული, წონიანი, დაუწონავი, მრავალი კიდეებითა და მარყუჟებით ან მის გარეშე).

მაშ, წავიდეთ. რა ვარიანტები გვაქვს მონაცემთა სტრუქტურებისთვის „გრაფიკის შესანახად“?

1. მატრიცული მონაცემთა სტრუქტურები

1.1 მიმდებარეობის მატრიცა. მიმდებარე მატრიცა არის მატრიცა, სადაც სტრიქონების და სვეტების სათაურები შეესაბამება გრაფიკის წვეროების რიცხვებს, ხოლო მისი თითოეული ელემენტის მნიშვნელობა a(i,j) განისაზღვრება წვეროებს შორის კიდეების არსებობით ან არარსებობით. i და j (ნათელია, რომ არამიმართული გრაფიკისთვის ასეთი მატრიცა სიმეტრიული იქნება, ან შეგვიძლია შევთანხმდეთ, რომ ყველა მნიშვნელობას ვინახავთ მხოლოდ მთავარი დიაგონალის ზემოთ). დაუწონავი გრაფიკებისთვის a(i,j) შეიძლება დაყენდეს i-დან j-მდე კიდეების რაოდენობით (თუ ასეთი კიდე არ არის, მაშინ a(i,j)= 0), ხოლო შეწონილი გრაფიკებისთვის ასევე წონით. (საერთო წონა) აღნიშნული კიდეების.

1.2 ინციდენტების მატრიცა. ამ შემთხვევაში, ჩვენი გრაფიკი ასევე ინახება ცხრილში, რომელშიც, როგორც წესი, მწკრივის ნომრები შეესაბამება მისი წვეროების რიცხვებს, ხოლო სვეტების ნომრები შეესაბამება წინასწარ დანომრილ კიდეებს. თუ წვერო და კიდე ერთმანეთს ემთხვევა, მაშინ შესაბამის უჯრედში იწერება არანულოვანი მნიშვნელობა (მიმართული გრაფიკებისთვის 1 იწერება, თუ წვერო და კიდე ინციდენტია, ორიენტირებული გრაფიკებისთვის - "1", თუ კიდე "გამოდის" წვეროდან და "-1", თუ "შედის" მასში (მისი დამახსოვრება საკმაოდ მარტივია, რადგან "მინუს" ნიშანი ასევე "შედის" რიცხვში "-1")). შეწონილი გრაფიკებისთვის, ისევ 1-ისა და -1-ის ნაცვლად, შეგიძლიათ მიუთითოთ კიდეების მთლიანი წონა.

2. აღრიცხვის მონაცემთა სტრუქტურები

2.1 მიმდებარეობის სია. ისე, როგორც ჩანს, აქ ყველაფერი მარტივია. გრაფის ყოველი წვერო, ზოგადად, შეიძლება ასოცირებული იყოს ნებისმიერი აღრიცხვის სტრუქტურასთან ( სია, ვექტორი, მასივი, ...), რომელიც შეინახავს მოცემული წვერის მიმდებარე ყველა წვეროს რიცხვებს. მიმართული გრაფიკებისთვის ასეთ ჩამონათვალს დავამატებთ მხოლოდ იმ წვეროებს, რომლებზეც არის „მიმართული“ კიდე მახასიათებლის წვეროდან. შეწონილი გრაფიკებისთვის განხორციელება უფრო რთული იქნება.

2.2 ნეკნების სია. საკმაოდ პოპულარული მონაცემთა სტრუქტურა. კიდეების სია, როგორც კაპიტანი ცხადი გვეუბნება, სინამდვილეში არის გრაფის კიდეების სია, რომელთაგან თითოეული მითითებულია საწყისი წვერით, ბოლო წვერით (მიმართული გრაფიკებისთვის აქ თანმიმდევრობა არ არის მნიშვნელოვანი, თუმცა გაერთიანებისთვის შეგიძლიათ. გამოიყენეთ სხვადასხვა წესები, მაგალითად, მიუთითეთ წვეროები გაზრდის მიზნით) და წონა (მხოლოდ შეწონილი გრაფიკებისთვის).

თქვენ შეგიძლიათ ნახოთ ზემოთ ჩამოთვლილი მატრიცული სიები უფრო დეტალურად (და ილუსტრაციებით), მაგალითად, აქ.

2.3 მიმდებარე მასივი. არ არის ყველაზე გავრცელებული სტრუქტურა. თავის არსში, ეს არის მიმდებარე სიების „შეფუთვის“ ფორმა ერთ აღრიცხვის სტრუქტურაში (მასივი, ვექტორი). ასეთი მასივის პირველი n (გრაფიკის წვეროების რაოდენობის მიხედვით) ელემენტები შეიცავს იმავე მასივის საწყის ინდექსებს, საიდანაც ზედიზედ იწერება მოცემულის მიმდებარე ყველა წვერო.

აქ ვიპოვე ყველაზე გასაგები (ჩემთვის) ახსნა: ejuo.livejournal.com/4518.html

3. მიმდებარეობის ვექტორული და ასოციაციური მიმდებარეობის მასივი

აღმოჩნდა, რომ ამ სტრიქონების ავტორი, არა პროფესიონალი პროგრამისტი, მაგრამ რომელიც პერიოდულად ეხებოდა გრაფიკებს, ყველაზე ხშირად ეხებოდა კიდეების სიებს. მართლაც, მოსახერხებელია, თუ გრაფიკს აქვს მრავალი მარყუჟი და კიდეები. ასე რომ, კიდეების კლასიკური სიების შემუშავებისას, მე ვთავაზობ ყურადღება მიაქციოთ მათ „განვითარებას/განშტოებას/მოდიფიკაციას/მუტაციას“, კერძოდ: მიმდებარეობის ვექტორს და მიმდებარეობის ასოციაციურ მასივს.

3.1 მიმდებარეობის ვექტორი

შემთხვევა (a1): დაუწონავი გრაფიკი

ჩვენ დავარქმევთ მიმდებარეობის ვექტორს დაუწონავი გრაფიკისთვის ლუწი რიცხვების მოწესრიგებულ სიმრავლეს (a[2i], a[2i+1],..., სადაც i არის დანომრილი c 0), რომელშიც რიცხვების თითოეული წყვილი არის a[2i], a[2i+1] განსაზღვრავს გრაფიკის კიდეს a[2i] და a[2i+1] წვეროებს შორის, შესაბამისად.
ჩანაწერის ეს ფორმატი არ შეიცავს ინფორმაციას იმის შესახებ, არის თუ არა გრაფიკი მიმართული (ორივე ვარიანტი შესაძლებელია). დიგრაფის ფორმატის გამოყენებისას კიდე ითვლება მიმართულად a[2i]-დან a[2i+1]-მდე. აქ და ქვემოთ: არამიმართული გრაფიკებისთვის, საჭიროების შემთხვევაში, შეიძლება გამოყენებულ იქნას წვეროების ჩაწერის თანმიმდევრობის მოთხოვნები (მაგალითად, რომ წვერო, რომელსაც აქვს მისთვის მინიჭებული რიცხვის ქვედა მნიშვნელობა, პირველ რიგში მოდის).

C++-ში მიზანშეწონილია მიუთითოთ მიმდებარე ვექტორი std::vector-ის გამოყენებით, აქედან გამომდინარეობს მონაცემთა სტრუქტურის სახელი.

შემთხვევა (a2): დაუწონავი გრაფიკი, კიდეების წონა მთელი რიცხვია

(a1 შემთხვევის ანალოგიით), ჩვენ ვუწოდებთ მიმდებარეობის ვექტორს შეწონილი გრაფისთვის მთელი კიდეების წონებით რიცხვების მოწესრიგებულ სიმრავლეს (დინამიური მასივი) (a[3i], a[3i+1], a[3i+2], ..., სადაც i არის დანომრილი c 0), სადაც a[3i], a[3i+1], a[3i+2] რიცხვების თითოეული „სამმაგი“ მიუთითებს გრაფის კიდეს a[3i] წვეროებს შორის. და a[3i+1], შესაბამისად, და მნიშვნელობა a [3i+2] არის ამ კიდის წონა. ასეთი გრაფიკი ასევე შეიძლება იყოს მიმართული ან არა.

შემთხვევა (ბ): დაუწონავი გრაფიკი, არამთლიანი კიდეების წონა

ვინაიდან შეუძლებელია ჰეტეროგენული ელემენტების შენახვა ერთ მასივში (ვექტორში), მაგალითად, შესაძლებელია შემდეგი განხორციელება. გრაფიკი ინახება ვექტორების წყვილში, რომელშიც პირველი ვექტორი არის გრაფიკის მიმდებარე ვექტორი წონების მითითების გარეშე, ხოლო მეორე ვექტორი შეიცავს შესაბამის წონებს (შესაძლებელია განხორციელება C++-ისთვის: std::წყვილი ). ამრიგად, პირველი ვექტორის 2i, 2i+1 ინდექსების ქვეშ წვეროების წყვილით განსაზღვრული კიდესთვის წონა ტოლი იქნება მეორე ვექტორის i ინდექსის ქვეშ მყოფ ელემენტს.

აბა, რატომ არის ეს საჭირო?

ისე, ამ სტრიქონების ავტორს ეს საკმაოდ გამოსადეგი აღმოჩნდა მრავალი პრობლემის გადასაჭრელად. კარგად, ფორმალური თვალსაზრისით, იქნება შემდეგი უპირატესობები:

• მიმდებარეობის ვექტორი, ისევე როგორც ნებისმიერი სხვა "აღრიცხვითი" სტრუქტურა, საკმაოდ კომპაქტურია, იკავებს ნაკლებ მეხსიერებას, ვიდრე მიმდებარე მატრიცა (მწირი გრაფიკებისთვის) და შედარებით მარტივია განხორციელება.
• გრაფიკის წვეროები, პრინციპში, ასევე შეიძლება აღინიშნოს უარყოფითი რიცხვებით. რა მოხდება, თუ საჭიროა ასეთი "გარყვნილება"?
• გრაფიკები შეიძლება შეიცავდეს რამდენიმე კიდეს და მრავალ მარყუჟს, სხვადასხვა წონით (დადებითი, უარყოფითი, თუნდაც ნულოვანი). აქ არანაირი შეზღუდვა არ არის.
• თქვენ ასევე შეგიძლიათ მიანიჭოთ კიდეებს სხვადასხვა თვისებები - მაგრამ მეტი ამის შესახებ იხილეთ განყოფილება 4.

თუმცა, უნდა ვაღიაროთ, რომ ეს "სიტი" არ გულისხმობს ზღვარზე სწრაფ წვდომას. და აქ Associative Adjacency Array მოდის სამაშველოში, რომელიც განიხილება ქვემოთ.

3.2 ასოციაციური მიმდებარეობის მასივი

ასე რომ, თუ კონკრეტულ ზღვარზე წვდომა, მისი წონა და სხვა თვისებები ჩვენთვის გადამწყვეტია და მეხსიერების მოთხოვნები არ გვაძლევს საშუალებას გამოვიყენოთ მიმდებარეობის მატრიცა, მაშინ მოდით ვიფიქროთ იმაზე, თუ როგორ შეგვიძლია შევცვალოთ მიმდებარეობის ვექტორი ამ პრობლემის გადასაჭრელად. ამრიგად, გასაღები არის გრაფის კიდე, რომელიც შეიძლება განისაზღვროს, როგორც მთელი რიცხვების მოწესრიგებული წყვილი. რას ჰგავს ეს? ეს არ არის გასაღები ასოციაციურ მასივში? და თუ ასეა, რატომ არ ვახორციელებთ მას? მოდით გვქონდეს ასოციაციური მასივი, სადაც თითოეული გასაღები - მთელი რიცხვების მოწესრიგებული წყვილი - ასოცირდება მნიშვნელობასთან - მთელ რიცხვთან ან რეალურ რიცხვთან, რომელიც განსაზღვრავს კიდის წონას. C++-ში მიზანშეწონილია ამ სტრუქტურის დანერგვა std::map კონტეინერის საფუძველზე (std::map , int> ან std::map , double>), ან std::multimap თუ მოსალოდნელია მრავალი კიდე. ისე, ჩვენ გვაქვს გრაფიკების შესანახი სტრუქტურა, რომელიც იკავებს ნაკლებ მეხსიერებას, ვიდრე "მატრიცული" სტრუქტურები, შეუძლია განსაზღვროს გრაფიკები მრავალი მარყუჟით და კიდეებით და არც კი აქვს მკაცრი მოთხოვნები წვეროს რიცხვების არანეგატიურობის შესახებ (არ ვიცი ვის სჭირდება ეს, მაგრამ მაინც).

4. მონაცემთა სტრუქტურები სავსეა, მაგრამ რაღაც აკლია

და ეს მართალია: მთელი რიგი ამოცანების გადაჭრისას, შეიძლება დაგჭირდეთ გრაფიკის კიდეებს გარკვეული მახასიათებლების მინიჭება და, შესაბამისად, მათი შენახვა. თუ შესაძლებელია ამ მახასიათებლების ცალსახად შემცირება მთელ რიცხვებამდე, მაშინ შესაძლებელია ასეთი „გრაფების შენახვა დამატებითი ფუნქციებით“ მიმდებარეობის ვექტორისა და ასოციაციური მიმდებარეობის მასივის გაფართოებული ვერსიების გამოყენებით.

მაშ ასე, გვქონდეს დაუწონავი გრაფიკი, რომლის თითოეული კიდესთვის აუცილებელია, მაგალითად, მთელი რიცხვებით მითითებული 2 დამატებითი მახასიათებლის შენახვა. ამ შემთხვევაში, შესაძლებელია განვსაზღვროთ მისი მიმდებარე ვექტორი, როგორც მთელი რიცხვების არა „წყვილების“, არამედ „კვარტეტების“ მოწესრიგებული სიმრავლე (a[2i], a[2i+1], a[2i+2], a. [2i+3]…), სადაც a[2i+2] და a[2i+3] განსაზღვრავს შესაბამისი კიდის მახასიათებლებს. კიდეების მთელი წონით გრაფიკისთვის, თანმიმდევრობა ზოგადად მსგავსია (ერთადერთი განსხვავება ის იქნება, რომ ატრიბუტები მიჰყვება კიდეების წონას და მითითებული იქნება ელემენტებით a[2i+3] და a[2i+4] , და თავად კიდე მითითებული იქნება არა 4, არამედ 5 შეკვეთილი რიცხვი). და არა მთელი კიდეების წონებით გრაფიკისთვის, ფუნქციები შეიძლება ჩაიწეროს მის დაუწონებელ კომპონენტში.

ასოციაციური მიმდებარე მასივის გამოყენებისას გრაფიკებისთვის მთელი კიდეების წონით, შესაძლებელია მნიშვნელობის სახით მიუთითოთ არა ერთი რიცხვი, არამედ რიცხვების მასივი (ვექტორი), რომელიც განსაზღვრავს, გარდა კიდის წონისა, ყველა სხვა საჭირო. მახასიათებლები. ამავდროულად, არამთლიანი წონის შემთხვევაში უხერხულობა იქნება მცურავი წერტილის მქონე ნიშნის მითითების აუცილებლობა (დიახ, ეს უხერხულობაა, მაგრამ თუ ამდენი ასეთი ნიშანი არ არის და თუ არ დააყენეთ ისინი ზედმეტად „სახიფათო“ ორმაგად, მაშინ შეიძლება არაფერი იყოს). ეს ნიშნავს, რომ C++-ში გაფართოებული ასოციაციური მიმდებარეობის მასივები შეიძლება განისაზღვროს შემდეგნაირად: std::map , std::vector> ან std::map , std:: ვექტორი, რომელშიც პირველი მნიშვნელობა "გასაღები-მნიშვნელობა-ვექტორში" იქნება კიდის წონა, შემდეგ კი განლაგებულია მისი მახასიათებლების რიცხვითი აღნიშვნები.

ლიტერატურა:

ზოგადად გრაფიკების და ალგორითმების შესახებ:

1. კორმენი, თომას ჰ., ლეიზერსონი, ჩარლზ აი., რივესტი, რონალდ ლ., სტეინი, კლიფორდი. ალგორითმები: მშენებლობა და ანალიზი, მე-2 გამოცემა: ტრანს. ინგლისურიდან – მ.: უილიამსის გამომცემლობა, 2011 წ.
2. ჰარარი ფრანკი. გრაფიკის თეორია. მ.: მირი, 1973 წ.
ავტორის მოხსენება იმავე ვექტორული და მიმდებარე კავშირების ასოციაციური მასივის შესახებ:
3. ჩერნოუხოვის ს.ა. მიმდებარეობის ვექტორი და ასოციაციური მიმდებარეობის მასივი, როგორც გრაფიკების წარმოდგენისა და შენახვის გზები / SA Chernouhov. მიმდებარეობის ვექტორი და მიმდებარეობის რუკა, როგორც მონაცემთა სტრუქტურები გრაფიკის წარმოსადგენად // საერთაშორისო სამეცნიერო და პრაქტიკული კონფერენციის სტატიების კრებული „ინოვაციური განვითარების შედეგების განხორციელების პრობლემები და მათი გადაჭრის გზები“ (სარატოვი, 14.09.2019 სექტემბერი, 2019 წ.). – სტერლიტამაკი: AMI, 65, გვ. 69-XNUMX
სასარგებლო ონლაინ წყაროები თემაზე:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

წყარო: www.habr.com