Алгоритъм на търсене по широчина

Обхождането в широчина задава две стойности на всеки връх

v

Разстояние, което дава минимален брой ръбове по всяка пътека от източника към връх $v$ ‍.
Връх предшественик на $v$ ‍ заедно с най-краткия път до изолирания връх. Предшественикът на изолирания връх е специална стойност, например null, която показва, че няма предшественик.

Ако съществува път между изолирания връх и върха

v

, то разстоянието на

v

е безкрайно и неговият предшественик има същата специална стойност като предшественика на изолирания връх.

Например ето един неориентиран граф с осем върха, номерирани от 0 до 7 – числата на върховете са записани под или над тях. Във всеки връх има две числа: разстоянието от изолирания връх, който е връх 3, последвано от неговия предшественик с най-кратък път от връх 3. Тирето показва null:

В този алгоритъм в началото задаваме разстоянието и предшественика на всеки връх със специална стойност (null). Започваме търсенето от началото и записваме разстояние 0. След това посещаваме всички съседи на изолирания връх и даваме на всеки съсед разстояние 1, като задаваме за негов предшественик изолирания връх. След това посещаваме всички съседи на върховете, чието разстояние е 1 и които все още не са били посетени, и даваме на тези върхове разстояние 2 и задаваме за предшественик върха, от който сме ги посетили. Продължаваме така, докато всички достъпни върхове от изолирания връх бъдат посетени, като винаги посещаваме всички върхове на разстояние

k

от изолирания връх преди да посетим всеки връх на разстояние

k + 1

Ето всички стъпки и визуализация за всяка стъпка от горния пример:

Започваме, като посетим връх 3 и зададем разстояние 0.
След това посещаваме върховете 2 и 6 и задаваме разстояние 1 и предшественик връх 3.
Започваме да посещаваме от върховете с разстояние 1 от изолирания връх, като стартираме от връх 2. От връх 2 посещаваме върховете 4 и 5, задаваме им разстояние 2 и предшественик – 2. Не посещаваме връх 3, защото той вече е посетен.
От връх 6 не посещаваме връх 5, защото той е посетен от връх 2, и връх 3.
Сега започваме да посещаваме върховете на разстояние 2 от изолирания връх. Започваме от връх 4. Връх 2 вече е посетен. Посещаваме връх 1, задаваме му разстояние 3 и предшественик връх 4.
От връх 5 не посещаваме никой от неговите съседи, защото вече са били посетени.
Сега започваме да посещаваме върховете на разстояние 3 от изолирания връх. Единственият такъв връх е 1. Неговите съседи, върховете 4 и 5, са били посетени. Но връх 0 не е. Посещаваме връх 0, задаваме разстоянието му на 4 и предшественика му на връх 1.
Сега започваме да посещаваме от върховете на разстояние 4 от изолирания връх. Това означава само връх 0 и неговия съсед връх 1, който вече е посетен. Готови сме!

Забележи, че, тъй като няма път от връх 3 към връх 7, търсенето никога не стига до връх 7. Разстоянието и предшественика му остават непроменени от първоначалните си стойности null.

Изникват няколко въпроса. Единият е как да определим дали един връх е бил посетен. Това е лесно – разстоянието на върха е null, докато не бъде посетен и не бъде зададена стойност за това разстояние. Следователно, когато обхождаме съседите на един връх, посещаваме само тези съседи, чието разстояние е null.

Другият въпрос е как да следим кои върхове са били посетени, но все още не са били отправна точка. Използваме опашка (queue), което е структура от данни, която ни позволява да вмъкваме и премахваме елементи, като изваденият елемент винаги е този, който е бил в опашката най-дълго. Наричаме това поведение първи вътре, първи вън. Опашката има три операции:

enqueue(obj) вмъква обект в опашката.
dequeue() изважда от опашката този обект, който е бил в нея най-дълго, и го връща като резултат.
isEmpty() връща true, ако в момента опашката не съдържа обекти, и false, ако в опашката има поне един обект.

Когато посетим даден връх, ние го поставяме в опашката. В началото поставяме изолирания връх, тъй като това винаги е първият връх, който посещаваме. За да решим кой връх да посетим след това, избираме върха, който е бил най-дълго в опашката и го изваждаме от нея – с други думи използваме върха, който е върнат от dequeue(). Ето как изглежда опашката във всяка стъпка за нашия примерен граф, заедно с предишната визуализация, показана за състоянията на опашката:

В началото опашката съдържа само връх 3 с разстояние 0.
Изваждаме връх 3 и вмъкваме върховете 2 и 6 – и двата с разстояние 1. Сега опашката съдържа връх 2 с разстояние 1 и връх 6 с разстояние 1.
Изваждаме връх 2 и вмъкваме върховете 4 и 5 – и двата с разстояние 2. Сега опашката съдържа връх 6 с разстояние 1, връх 4 с разстояние 2 и връх 5 с разстояние 2.
Изваждаме връх 6 и не вмъкваме други върхове. Сега опашката съдържа връх 4 с разстояние 2 и връх 5 с разстояние 2.
Изваждаме връх 4 и вмъкваме връх 1 с разстояние 3. Сега опашката съдържа връх 5 с разстояние 2 и връх 1 с разстояние 3.
Изваждаме връх 5 и не добавяме нови върхове. Сега опашката съдържа само връх 1 с разстояние 3.
Изваждаме връх 1 и доабвяме връх 0 с растояние 4. Сега опашката съдържа само връх 0 с разстояние 4.
Изваждаме връх 0 и не добавяме нови върхове. Сега опашката е празна. Тъй като опашката е празна, обхождането по ширина завършва.

Забележи, че във всеки момент опашката съдържа или всички върхове с еднакво разстояние, или върхове с разстояние

k

, последвани от върхове с разстояние

k + 1

. Така сме сигурни, че сме посетили всички върхове на разстояние

k

преди да посетим върховете с разстояние

k + 1

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.

Искаш ли да се присъединиш към разговора?

Вписване в профила

Сортирай по:

Все още няма публикации.

Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.