სიგანეში ძებნა (BFS)

როგორ იგებს ქსელი, ვინ არის შენი მე-2 დონის კონტაქტი? ის ტალღებად იკვლევს: ჯერ ყველას, ვინც ერთი ნაბიჯითაა დაშორებული, მერე ორით, მერე სამით. ეს სიგანეში ძებნაა, დეიქსტრასა და პრიმის ალგორითმების საფუძველი.

★ ლექცია: Graph_BFS · ზაზა გამეზარდაშვილი▶ ვიდეო საშუალო⏱ 20 წთ

←ეყრდნობა

3რიგი (FIFO) და დეკიBFS არის რიგი მოქმედებაში: სწორედ FIFO წესი ქმნის ტალღას.6გრაფის წარმოდგენაBFS რიგიდან ამოღებული ყოველი წვეროს მოსაზღვრე წვეროთა სიას გადაუყვება.5ხეები: ცნებები, თვისებები, შემოვლებიხეზე BFS დონეების მიხედვით შემოვლაა; გრაფზე მას მონახულებულთა მასივი ემატება.

გზას უხსნის→

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

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

ისწავლე

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

01ამოცანის დასმა და ტალღა

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

ლექცია BFS-ს ტალღურ ალგორითმს უწოდებს: ჯერ ვპოულობთ ყველა წვეროს, რომელიც s-დან ერთი წიბოთია დაშორებული, შემდეგ ორი წიბოთი დაშორებულებს და ა.შ., როგორც წყალზე გავრცელებული ტალღა. ლექციის გრაფზე s = 4-ით: ჯერ 5, 2 და 3; მერე 7, 1, 6 და 8; ბოლოს 9.

რადგან ტალღა ჯერ ახლო წვეროებს აღწევს, BFS-ით ნაპოვნი მანძილი საბოლოოა: ის უკვე უმოკლესია და მომდევნო ბიჯებზე აღარ უმჯობესდება.

ლექციის გრაფი, შეღებილი საწყისი 4 წვეროდან მანძილის მიხედვით.

02წვეროების ფერები, რიგი, d[], p[], used[]

ალგორითმის მუშაობის თვალის სადევნებლად BFS წვეროებს სამ ფერად ღებავს:

თეთრი: ჯერ აღმოუჩენელი (დასაწყისში ყველა);
რუხი: აღმოჩენილია და რიგში ელოდება;
შავი: მისი ყველა მეზობელი უკვე აღმოჩენილია.

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

მოსაცდელი არის FIFO რიგი („პირველი მოვიდა, პირველი წავიდა“): ყოველთვის ყველაზე ძველ წვეროს ვიღებთ. სწორედ ეს ქმნის ტალღას, რადგან x მანძილზე მყოფი ყველა წვერო რიგიდან გამოდის, სანამ x + 1 მანძილზე მყოფი რომელიმე გამოვა. ლექციის კოდი სამ მასივს ინახავს:

d[v]: მანძილი s-დან;
p[v]: v-ს მშობელი სიგანეში ძებნის ხეში (s-ისთვის nil, ანუ −1);
used[v]: აღმოჩენილია თუ არა v (რუხი ან შავი).

რიგი მე-3 იტერაციის შემდეგ: მანძილები სათავიდან ბოლოსკენ არ კლებულობს.

03ბიჯ-ბიჯ ლექციის გრაფზე

ციკლი მოკლეა: რიგის სათავიდან ვიღებთ v-ს; v-ს ყოველი მეზობლისთვის to, რომელიც used არ არის, ვნიშნავთ მას, ვწერთ d[to] = d[v] + 1 და p[to] = v, და ვამატებთ რიგის ბოლოში. შემდეგ v შავდება.

ლექციის გრაფზე s = 4-ით:

ინიციალიზაცია: რიგი [4], d[4] = 0, p[4] = nil;
იტერაცია 1: ამოვიღეთ 4, აღმოვაჩინეთ 5, 2, 3 მანძილით 1 → [5, 2, 3];
იტერაცია 2: ამოვიღეთ 5, აღმოვაჩინეთ 7 და 1 მანძილით 2 → [2, 3, 7, 1];
იტერაცია 3: ამოვიღეთ 2, აღმოვაჩინეთ 6 → [3, 7, 1, 6];
იტერაცია 4: ამოვიღეთ 3, აღმოვაჩინეთ 8 → [7, 1, 6, 8];
იტერაცია 5: ამოვიღეთ 7, აღმოვაჩინეთ 9 მანძილით 3 → [1, 6, 8, 9];
დანარჩენი იტერაციები იღებს 1-ს, 6-ს, 8-ს და 9-ს და ახალს ვეღარაფერს პოულობს.

საბოლოო ცხრილები 1…9 წვეროებისთვის: d = 2, 1, 1, 0, 1, 2, 2, 2, 3 და p = 5, 4, 4, nil, 4, 2, 5, 3, 7.

იტერაცია 3: დამუშავდა წვერო 2 და აღმოაჩინა 6.

04სიგანეში ძებნის ხე და ალგორითმის კორექტულობა

ყოველი წვერო რიგში ერთხელ ხვდება, ამიტომ მას ზუსტად ერთი მშობელი ჰყავს: წიბოები (p[v], v) ქმნიან სიგანეში ძებნის ხეს. წიბო 1–7 მასში არ შედის, რადგან როცა 7 რიგიდან ამოვიდა, 1 უკვე აღმოჩენილი იყო. t-მდე უმოკლესი გზის ამოსაბეჭდად t-დან მშობლებს მივყვებით და ბოლოს გზას ვაბრუნებთ: 9-ისთვის ეს არის 9 → 7 → 5 → 4, შებრუნებით 4 → 5 → 7 → 9, სამი წიბო = d[9].

რატომ არის მანძილები უმოკლესი? ლექცია ამას ორ ნაბიჯად ამტკიცებს:

ლემა: რიგში წვეროების მანძილები არაკლებადია და ერთმანეთისგან არაუმეტეს 1-ით განსხვავდება (მე-3 იტერაციაზე რიგს 3, 7, 1, 6 აქვს d = 1, 2, 2, 2). ინდუქციით: x მანძილის მქონე v-ს ამოღებისას მისი ახალი მეზობლები x + 1 მანძილით ბოლოში ემატება.
თეორემა: დავუშვათ, რომელიმე d[u] არასწორია; ავიღოთ ასეთი უახლოესი u, რომლის მშობელია v სიგანეში ძებნის ხეში, ნამდვილ უმოკლეს გზაზე კი წინა წვეროა w. მაშინ d[w] < d[v], ამიტომ ლემის თანახმად w რიგიდან v-ზე ადრე გამოვიდოდა და u-ს პირველი ის აღმოაჩენდა. წინააღმდეგობა. რ.დ.გ.

05ასიმპტოტიკა და BFS-ის გამოყენება

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

ლექცია კლასიკურ გამოყენებებს ჩამოთვლის:

უმოკლესი გზები ერთი წვეროდან ყველა დანარჩენამდე უწონო გრაფში;
ბმული კომპონენტები: BFS ვუშვებთ ყოველი ჯერ მოუნიშნავი წვეროდან, თითო კომპონენტზე ერთხელ;
სვლების უმცირესი რაოდენობა თამაშში ან თავსატეხში, რომლის მდგომარეობები წვეროებია, მაგალითად ლაბირინთიდან გამოსვლა;
0-1 BFS 0 ან 1 წონის წიბოებისთვის: 0-წიბოს შემდეგ წვერო დეკის დასაწყისში ჩავსვათ, 1-წიბოს შემდეგ ბოლოში;
უმოკლესი ციკლი ორიენტირებულ გრაფში; ყველა წვერო, რომელიც დევს a→b რომელიმე უმოკლეს გზაზე (BFS ორივე ბოლოდან და შემოწმება DA[v] + DB[v] = DA[b]); უმოკლესი ლუწი სიგრძის გზა (წვერო, ლუწ-კენტობა) მდგომარეობებით.

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

ლექციის C++ კოდიC++

მე-18 სლაიდი: წვერო used მასივში რიგში ჩასმისთანავე ინიშნება, იღებს d[to] = d[v] + 1 მანძილს და მშობელს p[to]-ში იმახსოვრებს, რომლის მიხედვითაც კოდის მეორე ნაწილი გზას უკუღმა აღადგენს. მეორე ნაწილში `to` ციკლის ცვლადი აღარ არის: ეს ის სამიზნე წვეროა, რომლამდეც გზა გვაინტერესებს, ამიტომ ამ ნაწილამდე ის ცალკე უნდა გამოვაცხადოთ და წავიკითხოთ.

vector < vector<int> > g; // გრაფი
int n, s; // n - წვეროების რაოდენობა, s - საწყისი წვერო (წვეროები გადანომრილია ნულიდან)
// გრაფის კითხვა
...
queue<int> q;
q.push (s);
vector<bool> used (n);
vector<int> d(n), p(n); // d[n] - ვექტორი მანძილებისთვის, p[n] - მშობლების ვექტორი
used[s] = true;        p[s] = -1;
while (!q.empty()) {
    int v = q.front();    q.pop();
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (!used[to]) {
            used[to] = true;
            q.push (to);
            d[to] = d[v] + 1;
            p[to] = v;
        }
    }
}
// გზის აღდგენა
if (!used[to]) cout << "No path!";
else {
    vector<int> path;
    for (int v=to; v!=-1; v=p[v])
        path.push_back (v);
    reverse (path.begin(), path.end());
    cout << "Path: ";
    for (size_t i=0; i<path.size(); ++i)
        cout << path[i] + 1 << " ";
}

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

დროO(V + E)

მეხსიერება (რიგი, d, p, used)O(V)

გზის აღდგენა p[]-დანO(path length)

დაიმახსოვრე

FIFO რიგის წყალობით BFS გრაფს ტალღებად, დონე-დონე იკვლევს საწყისი წვეროდან.
უწონო გრაფში წვეროს პირველი აღმოჩენა მის უმოკლეს მანძილს იძლევა; p[] ინახავს სიგანეში ძებნის ხეს გზების აღსადგენად.
ყოველი წვერო და ყოველი წიბო ერთხელ მუშავდება, ამიტომ BFS O(V + E) დროში მუშაობს.

უყურე

ლექცია ვიდეოს სახით.

▶

ლექცია, ანიმაციით

ვიდეო ლექციას სლაიდ-სლაიდ მიჰყვება: იგივე მაგალითი, იგივე აღნიშვნები. უყურე ვიზუალიზატორთან თამაშამდე ან მის შემდეგ.

▶ ვიდეოს გვერდი ▣ პრეზენტაციად გახსნა

ითამაშე

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

👀 რას უყურო: თვალი ადევნე რიგს: წვეროები მარცხნიდან გამოდის იმ რიგით, რომლითაც აღმოაჩინეს, და მათი d მნიშვნელობები არ კლებულობს. შემდეგ აირჩიე სხვა საწყისი წვერო და შეადარე სიგანეში ძებნის ხეები.

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

გრაფი (საწყისი წვერო: 4)

თეთრი: აღმოუჩენელირუხი: რიგშიაშავი: დასრულებულიBFS-ის ხის წიბო

რიგი (FIFO)

მდგომარეობა

v	1	2	3	4	5	6	7	8	9
d[] მანძ.	∞	∞	∞	0	∞	∞	∞	∞	∞
p[] მშობ.	∞	∞	∞	nil	∞	∞	∞	∞	∞
used[]	0	0	0	1	0	0	0	0	0

ვიწყებთ საწყისი 4 წვეროდან: d[4] = 0, ვნიშნავთ და ვამატებთ რიგში. ის რუხდება.

ფსევდოკოდი

 1 q.push(s); used[s]=1; d[s]=0; p[s]=-1 2 while (!q.empty()) { 3   v = q.front(); q.pop() 4   for (u in adj[v]) { 5     if (!used[u]) { 6       used[u] = 1 7       d[u] = d[v]+1; p[u] = v 8       q.push(u) 9 } } }  // d[] = shortest distances

1 / 1

შეამოწმე

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

№1

ლექციის გრაფზე s = 4-დან, როგორია რიგი მე-2 იტერაციის შემდეგ (დამუშავდა წვერო 5)?

№2

რატომ იძლევა ჩვეულებრივი BFS არასწორ მანძილებს, როცა წიბოებს სხვადასხვა წონა აქვს?

№3

უმოკლესი გზა 1000 × 1000 ბადისებრ ლაბირინთში, სვლა ზემოთ, ქვემოთ, მარცხნივ ან მარჯვნივ. რა ღირს BFS?

ივარჯიშე

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

CSESMessage Route დამწყები↗CSESLabyrinth საშუალო↗LeetCodeRotting Oranges საშუალო↗LeetCodeShortest Path in Binary Matrix საშუალო↗CSESMonsters მოწინავე↗