Пошук по графу

У комп'ютерних науках, пошук по графу (або обхід графа) це процес проходження (перевірки або оновлення) кожної вершини графа. Такі алгоритми пошуку класифікують відповідно до порядку проходження вершин. Пошук по дереву є особливим випадком пошуку по графу.

Надмірність

На відміну від пошуку по дереву, пошук по графу може потребувати проходження деяких вершин більше ніж один раз, оскільки не обов'язково є відомості, при переході на вершину, що вона вже була перевірена. З тим як граф стає більш щільним, ця надмірність стає проявлятись більше, що призводить до збільшення необхідного часу на обчислення.

Таким чином, зазвичай краще запам'ятовувати які вершини було вже пройдено алгоритмом, так щоб вершини не перевірялися часто, якщо це можливо (або таке запам'ятовування дозволяє уникнути найгіршої поведінки — нескінченного пошуку по циклу). Це можна зробити за допомогою асоціації з кожною вершиною «колір» або стан «проходження» вершини під час пошуку, який потім помічається і оновлюється алгоритмом при проходженні кожної вершини графа.

Якщо вершина вже була пройдена, вона ігнорується і пошук у цьому напрямі далі не продовжується; якщо ні, алгоритм перевіряє й оновлює вершини і йде далі шляхом пошуку.

Алгоритми пошуку по графу

Пошук у глибину

Пошук у глибину по графу, це алгоритм проходження скінченного графа. Алгоритм проходить наступні дочірні вершини, перш ніж буде проходити вершини того ж рівня; таким чином, він проходить граф у глибину спершу ніж буде проходити вершини в ширину. Стек (зазвичай це програмний стек виклику при роботі з рекурсією) є основним вузьким місцем при використанні цього алгоритму.

Алгоритм починає пошук із вибраної вершини «кореня»; і потім в ітеративному порядку проходить від поточної вершини до наступної, невідвіданої вершини, до тих пір доки він не може більше знайти не дослідженої вершини для переходу кудись. Алгоритм потім здійснює рух назад по вже пройденим вершинам, доки не знайде наступну вершину, що ще не була пройдена. Тоді він пройде новий маршрут пошуку як у попередньому кроці, рухаючись назад кожного разу доки не зустріне кінець, і закінчить пошук лише коли рух назад призвів знов до вершини «кореня», що була на самому початку.

Пошук у ширину

Пошук у ширину це інша техніка пошуку по скінченному графу. Цей алгоритм проходить суміжні вершини перш ніж переходити до дочірніх вершин, і як процес пошуку використовується черга. Цей алгоритм часто використовується для пошуку найкоротшого шляху від одної вершини до іншої.

Примітки