ციკლები, ტოპოლოგიური სორტირება, ორწილადობა

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

საშუალო⏱ 14 წთ

←ეყრდნობა

6სიღრმეში ძებნა (DFS)ციკლების პოვნა და ტოპოლოგიური რიგი DFS-ის შესვლისა და გამოსვლის დროებიდან იკითხება.6სიგანეში ძებნა (BFS)ორწილადობის შემოწმება წვეროებს შრეებად ღებავს, BFS-ის ტალღების მიხედვით.

გზას უხსნის→

10დპ-ის საფუძვლები: მემოიზაცია და ცხრილიდპ-ის მდგომარეობები აციკლურ გრაფს ქმნის და ცხრილი ტოპოლოგიური რიგით უნდა შეივსოს.

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

ისწავლე

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

01ციკლები ორიენტირებულ გრაფში

ორიენტირებულ გრაფში „მივედი ნანახ წვეროსთან“ ციკლის დასამტკიცებლად საკმარისი არ არის: ეს წვერო შეიძლება სხვა განშტოებაზე უკვე დასრულებულიყო. სამივე ფერი გვჭირდება. DFS-ის დროს u-ში ვუყურებთ ყოველ წიბოს u → w:

w თეთრია: ხის წიბოა, რეკურსიით ჩავდივართ;
w რუხია: w ჯერ კიდევ რეკურსიის სტეკზეა, u-ს წინაპარია, ამიტომ გზა w → … → u და წიბო u → w ერთად ციკლს ქმნის;
w შავია: w და მის ქვემოთ ყველაფერი დასრულებულია; აქ ციკლი არ გადის.

კურსების გრაფში DFS-ის გზა 1 → 2 → 4 → 5 რუხია, როცა ახალ წიბოს 5 → 1 (AI → Intro) ვხვდებით. წვერო 1 რუხია, ე.ი. ციკლი ვიპოვეთ და სასწავლო გეგმა ვერ იარსებებს. ციკლის ამოსაბეჭდად შევინახოთ მშობლები და u-დან w-მდე უკან გავიაროთ.

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

02ტოპოლოგიური სორტირება DFS-ით

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

DFS ამას თითქმის უფასოდ იძლევა. როცა წვერო სრულდება (შავდება), ყველაფერი, რაზეც ის მიუთითებს, უკვე დასრულებულია. ამიტომ წვეროები კლებადი tout-ის მიხედვით ჩამოვწეროთ: დასრულებისას ყოველი წვერო სიის ბოლოში დავამატოთ, ბოლოს კი სია შევაბრუნოთ. კურსების DAG-ზე Intro-დან დაწყებით: პირველი სრულდება AI, მერე Algo, DB, DataStr, Discrete და ბოლოს Intro. შებრუნებით: Intro, Discrete, DataStr, DB, Algo, AI.

გარე ციკლი ყველა წვეროზე გაუშვი და არა მხოლოდ ერთი საწყისიდან, და რუხი წვეროს შემოწმება შეინარჩუნე: თუ ციკლი გამოჩნდა, ვაცხადებთ, რომ რიგი არ არსებობს. დრო O(V + E). ტოპოლოგიური რიგი, როგორც წესი, ერთადერთი არ არის; ნებისმიერი რიგი, სადაც ყველა ისარი წინ მიუთითებს, სწორია.

კურსების DAG ტოპოლოგიური რიგით: ყოველი ისარი მარჯვნივ მიუთითებს.

03კანის ალგორითმი: რიგით

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

თუ ყველა V წვერო გამოვიდა, ტოპოლოგიური რიგი გვაქვს. თუ რიგი ნაადრევად დაცარიელდა, დარჩენილი წვეროები ციკლზე ან ციკლის შემდეგ დგანან, ამიტომ კანის ალგორითმი ციკლსაც აღმოაჩენს. დრო O(V + E).

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

04ორწილადია თუ არა გრაფი?

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

შესამოწმებლად ვცდილობთ გრაფის 2 ფერით შეღებვას BFS-ით ან DFS-ით: საწყისს ვაძლევთ ფერს 0, ყოველ მეზობელს საპირისპიროს და ა.შ. თუ ოდესმე შეგვხვდება წიბო, რომლის ორივე ბოლო უკვე ერთი ფერისაა, გრაფი ორწილადი არ არის. ყველა კომპონენტის დასაფარად ძებნას ყოველი შეუღებავი წვეროდან ვიწყებთ. O(V + E).

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

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

ციკლის აღმოჩენა (3 ფერი)O(V + E)

ტოპოლოგიური სორტირება (DFS ან კანი)O(V + E)

ორწილადობის შემოწმებაO(V + E)

დაიმახსოვრე

ორიენტირებულ გრაფში წიბო რუხ წვეროზე, რომელიც ჯერ კიდევ DFS-ის სტეკზეა, ციკლს ამტკიცებს.
DFS-ის დასრულების შებრუნებული რიგი DAG-ის ტოპოლოგიური რიგია; კანის რიგიც იძლევა მას და ციკლსაც აღმოაჩენს.
გრაფი ორწილადია მაშინ და მხოლოდ მაშინ, როცა 2 ფერით შეიღებება, ანუ როცა კენტი ციკლი არ აქვს; BFS ან DFS ამას O(V + E)-ში ამოწმებს.

ითამაშე

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

👀 რას უყურო: უყურე რიგის ზოლს: კურსი თავში მხოლოდ დასრულებისას ემატება. შემდეგ დამატებითი წიბო 5 → 1 DAG-ს ციკლად აქცევს.

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

კურსების DAG (ორიენტირებული)

1 Intro → 2 DataStr, 3 Discrete · 2 → 4 Algo, 6 DB · 3 → 4 · 4 → 5 AI

ტოპოლოგიური რიგი

∅

კურსების წინაპირობების ორიენტირებული აციკლური გრაფი (DAG). ტოპოლოგიური სორტირება კურსებს ისე ალაგებს, რომ ყოველი წინაპირობა მასზე დამოკიდებულ კურსამდე მოდის.

ფსევდოკოდი

 1 topological sort of a DAG: 2   dfs(u): for each edge u→w, recurse on unvisited w 3   on finishing u, prepend u to the order 4 reverse finish order = valid dependency order 5 if dfs meets a gray vertex → cycle → no order exists

1 / 1

შეამოწმე

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

№1

DFS DAG-ის წვეროებს ამთავრებს რიგით C, E, B, D, A. რომელია ტოპოლოგიური რიგი?

№2

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

№3

რომელი გრაფი არ არის ორწილადი?

ივარჯიშე

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

LeetCodeCourse Schedule საშუალო↗LeetCodeIs Graph Bipartite? საშუალო↗CSESBuilding Teams საშუალო↗CSESCourse Schedule საშუალო↗CSESRound Trip საშუალო↗