გრაფის წარმოდგენა

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

დამწყები⏱ 8 წთ

←ეყრდნობა

5ხეები: ცნებები, თვისებები, შემოვლებიხე ბმული გრაფია ციკლების გარეშე; გრაფი ამ შეზღუდვას უბრალოდ ხსნის.1მასივები და დინამიური მასივებიმოსაზღვრე წვეროთა სია დინამიური მასივების მასივია, თითო ყოველ წვეროზე.

გზას უხსნის→

6სიგანეში ძებნა (BFS)BFS რიგიდან ამოღებული ყოველი წვეროს მოსაზღვრე წვეროთა სიას გადაუყვება.8ბელმან-ფორდი და უარყოფითი წიბოებიის უბრალოდ V − 1-ჯერ გადაუყვება წიბოთა სიას.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01წვეროები, წიბოები და გრაფის სახეები

გრაფი G = (V, E) არის წვეროების სიმრავლე და წიბოების სიმრავლე, სადაც ყოველი წიბო ორ წვეროს აერთებს. V-თი წვეროების რაოდენობასაც აღვნიშნავთ, E-თი კი წიბოებისას.

არაორიენტირებული: u–v წიბოზე ორივე მიმართულებით შეიძლება სვლა (მეგობრობა, ორმხრივი გზა).
ორიენტირებული: u→v წიბოს მიმართულება აქვს (ვინმეს გამოწერა, „A კურსი B-მდე უნდა გაიარო“).
წონადი: ყოველ წიბოს რიცხვი აწერია: სიგრძე, ფასი, დრო.

კიდევ ორი საჭირო ცნება. წვეროს ხარისხი მასთან დაკავშირებული წიბოების რაოდენობაა. გრაფი მეჩხერია, როცა E V-სთან ახლოსაა, და მკვრივი, როცა E V²-ს უახლოვდება. რეალური გრაფების უმეტესობა (გზები, ვები, მეგობრობები) მეჩხერია. ხე კი უკვე ნაცნობი კერძო შემთხვევაა: ბმული, არაორიენტირებული, ციკლების გარეშე, E = V − 1.

02მოსაზღვრეობის მატრიცა

ყველაზე პირდაპირი გზა V×V ცხრილია: M[u][v] = 1, თუ u–v წიბო არსებობს, სხვა შემთხვევაში 0. წონადი გრაფისთვის ვინახავთ წონას, „წიბოს არარსებობისთვის“ კი, მაგალითად, ∞-ს. არაორიენტირებულ გრაფში ყოველი წიბო ორ უჯრას ავსებს, M[u][v]-ს და M[v][u]-ს, ამიტომ მატრიცა სიმეტრიულია.

ძლიერი მხარე: კითხვა „არის თუ არა წიბო 2-სა და 5-ს შორის?“ მასივში ერთი მიმართვაა, O(1), კოდი კი ელემენტარულია. ფლოიდ-ვორშელი და გრაფებზე დინამიური პროგრამირების ბევრი ხრიკი ბუნებრივად მატრიცაზე იწერება.

სუსტი მხარე: მატრიცას ყოველთვის V² მეხსიერება სჭირდება, u-ს მეზობლების ჩამოსათვლელად კი მთელი სტრიქონი უნდა გადავიაროთ, O(V), თუნდაც u-ს მხოლოდ ორი მეზობელი ჰყავდეს. V = 100 000-ისთვის მატრიცაში 10¹⁰ უჯრაა: შეუძლებელია. პრაქტიკული წესი: მატრიცა კარგია რამდენიმე ათას წვერომდე, ან როცა გრაფი ისედაც მკვრივია.

03მოსაზღვრე წვეროთა სია და წიბოთა სია

მოსაზღვრე წვეროთა სია ყოველი წვეროსთვის მისი მეზობლების სიას ინახავს: vector<vector<int>> g(n); და ყოველი u–v წიბოსთვის g[u].push_back(v); g[v].push_back(u);. მეხსიერება არაორიენტირებული გრაფისთვის V + 2E-ია (ორიენტირებულისთვის V + E), u-ს მეზობლების მონახულება კი ზუსტად deg(u) ღირს, ზედმეტი ნულების გარეშე. BFS, DFS და დეიქსტრა სწორედ ამას აკეთებენ მთელი დრო, ამიტომ ყველა სიას იყენებს. წონებისთვის ვინახავთ წყვილებს: vector<vector<pair<int,int>>>.

წიბოთა სია კიდევ უფრო მარტივია: უბრალოდ E წყვილი (u, v), შესაძლოა წონებით. ამოცანების უმეტესობა შემავალ მონაცემებს ზუსტად ამ ფორმით გაძლევს, და ეს სწორი ფორმაა, როცა ალგორითმი წიბოებს ამუშავებს და არა წვეროებს: კრასკალი წიბოთა სიას წონით ალაგებს, ბელმან-ფორდი კი მასზე ისევ და ისევ გადის.

ჩვეულებრივ წიბოთა სიას შესავლიდან ვკითხულობთ და მისგან მაშინვე ვაგებთ მოსაზღვრე წვეროთა სიებს.

04რომელი ავირჩიოთ

იკითხე, რას აკეთებს შენი ალგორითმი ყველაზე ხშირად:

დადის წვეროდან მის მეზობლებთან (BFS, DFS, დეიქსტრა, პრიმი, ტოპოლოგიური სორტირება): მოსაზღვრე წვეროთა სია, O(V + E) მეხსიერება და დრო;
ხშირად კითხულობს „არის თუ არა u–v წიბო?“, ან V პატარაა და გრაფი მკვრივი (ფლოიდ-ვორშელი, ბიტმასკური DP წვეროებზე): მატრიცა;
წიბოებს სათითაოდ ან დალაგებული რიგით ამუშავებს (კრასკალი, ბელმან-ფორდი): წიბოთა სია.

ორი ხაფანგი. ინდექსაცია: ამოცანებში წვეროები ჩვეულებრივ 1-დან ინომრება, ამიტომ გამოყავი n + 1 სია ან წაკითხვისას გამოაკელი 1. არაორიენტირებულ გრაფში კი ორივე მიმართულება დაამატე; მეორე push_back-ის დავიწყება გრაფებში ყველაზე გავრცელებული შეცდომაა.

ზოგი გრაფი საერთოდ არ საჭიროებს შენახვას. ბადისებრ ლაბირინთში (r, c) უჯრის მეზობლები ადგილზევე გამოითვლება: (r ± 1, c) და (r, c ± 1).

ფასი ერთი შეხედვით

მატრიცა: მეხსიერებაO(V²)

მატრიცა: არის u–v წიბო?O(1)

მოსაზღვრე წვეროთა სია: მეხსიერებაO(V + E)

მოსაზღვრე წვეროთა სია: u-ს მეზობლებიO(deg u)

დაიმახსოვრე

მოსაზღვრეობის მატრიცა კითხვას „არის თუ არა u–v წიბო?“ O(1)-ში პასუხობს, მაგრამ ყოველთვის V² მეხსიერება სჭირდება.
მოსაზღვრე წვეროთა სიები O(V + E) ღირს და ყოველ წვეროს მეზობლებს პირდაპირ აძლევს, ამიტომ იყენებენ მათ BFS, DFS და დეიქსტრა.
წიბოთა სია შესავლის ჩვეული ფორმატია და სწორი არჩევანია წიბოებზე ორიენტირებული ალგორითმებისთვის, როგორებიცაა კრასკალი და ბელმან-ფორდი.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: ყოველი გამოჩენილი წიბო მატრიცაში ორ უჯრას და სიებში ორ ჩანაწერს წერს. ბოლოს შეადარე მატრიცის 25 უჯრა სიების 12 ჩანაწერს.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

გრაფი

მოსაზღვრეობის მატრიცა

	1	2	3	4	5
1	0	0	0	0	0
2	0	0	0	0	0
3	0	0	0	0	0
4	0	0	0	0	0
5	0	0	0	0	0

მოსაზღვრე წვეროთა სია

წიბოთა სია

∅

გრაფი წიბოებით დაკავშირებული წვეროებია. მისი შენახვის ორი სტანდარტული გზა არსებობს. ვუყუროთ ორივეს შევსებას, სანამ წიბოებს ვამჟღავნებთ.

ფსევდოკოდი

 1 a graph = vertices V + edges E 2 adjacency matrix: M[u][v] = 1 if edge u–v      (V×V) 3 adjacency list: list[u] = neighbours of u      (V + E) 4 edge exists? matrix O(1)  ·  list O(degree) 5 iterate neighbours: list wins → BFS/DFS/Dijkstra use lists

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

გზების ქსელს 200 000 გზაჯვარედინი და 500 000 გზა აქვს, მასზე BFS უნდა გაუშვა. რომელ წარმოდგენას აირჩევ?

№2

არაორიენტირებულ გრაფს 5 წვერო და 6 წიბო აქვს. სულ რამდენი ჩანაწერია მის მოსაზღვრე წვეროთა სიებში?

№3

კრასკალის ალგორითმი წიბოებს იაფიდან ძვირისკენ ამუშავებს. რა არის მისთვის ბუნებრივი შემავალი მონაცემები?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeFind Center of Star Graph დამწყები↗LeetCodeFind the Town Judge დამწყები↗LeetCodeFind if Path Exists in Graph დამწყები↗LeetCodeNumber of Provinces საშუალო↗