Побудова дерева обходу в ширину в середовищі програмування delphi

Перш ніж приступити до розгляду чергового delphi-проекту, що реалізує алгоритм обходу неорієнтованого графа, а якщо бути більш точним, то алгоритму обходу неорієнтованого графа в ширину, нагадаємо собі основну стратегію його роботи. Отже, для деякої вершини графа, зазначеної як стартова, проглядаються всі не відвідані її нащадки. На наступному кроці, не відвідані нащадки нащадків і так далі. Тобто, алгоритм пошуку в ширину перераховує всі досяжні вершини з початкової в порядку зростання їх віддаленості від неї і закінчує свою роботу, коли всі досяжні вершини пройдені.

Після того, як з теорією розібралися, перейдемо до розгляду delphi-проекту. Отже, після запуску програми, на екрані появиться форма наступного вигляду.

Пошук в ширину на delphi

Головне вікно проекту "Побудова дерева обходу в ширину для неорієнтованого графа"

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

Читати повністю

Побудова дерева обходу в глибину в середовищі програмування delphi

Delphi-програма реалізує один з найвідоміших алгоритмів обходу графа, а саме пошук в глибину. Основна суть даного алгоритму полягає в наступному: рухатися вглиб, поки це можливо (є не пройдені ребра), і повертатися і шукати інший шлях, коли таких ребер немає. Відмітимо, що така процедура виконується до тих пір, поки всі вершини, досяжні з вихідної не будуть переглянутими. Якщо після цього залишаються не переглянуті вершини, вибирають одну з них і для неї процес обходу графа в глибину повторюється.

Головна форма розглядуваного delphi-проекту ділиться на дві частини і складається з панелі інструментів  та графічного редактора. Розглянемо призначення кожної з них більш детально.

Читати повністю

Обхід графа в ширину

Пошук в ширину — один із базових алгоритмів, що є основою багатьох інших. Наприклад, алгоритм Дейкстри пошуку найкоротших шляхів з одної вершини і алгоритм Прима пошуку мінімального остового дерева можуть розглядатися як узагальнення пошуку в ширину. Згідно з цим алгоритмом обхід вершин заданого графа  здійснюється в порядку їх віддаленості від деякої заздалегідь обраної, або зазначеної як початкова, вершини  (називається коренем пошуку в ширину). Інакше кажучи, спочатку відвідується сама вершина , потім всі вершини, суміжні з , тобто ті, які знаходяться від неї на відстані в одне ребро, потім вершини, що знаходяться від  на відстані в два ребра, і так далі.

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

Пошук в ширину в неорієнтованому графі

Розглянемо алгоритм пошуку в ширину із заданої стартової вершини . Отже, спочатку всі вершини позначаються як непройдені. Першою відвідується вершина , вона стає єдиною пройденою активною вершиною. На наступному кроці, досліджуються ребра, інцидентні даній вершині. У загальному випадку, при такому дослідженні, можливі два варіанти подальших дій:

Читати повністю

Обхід графа в глибину

Пошук в глибину (або обхід в глибину) є одним з основних і найбільш часто вживаних алгоритмів обходу всіх вершин і ребер графа. Згідно з цим алгоритмом обхід здійснюється за наступним правилом: у графі вибираємо довільну вершину, наприклад , і починаємо з неї пошук. Початкова вершина  (називається коренем пошуку в глибину) після цього вважається пройденою. На наступному кроці, вибираємо ребро , інцидентне вершині  (орієнтуємо при цьому його напрямок з  в ), і з його допомогою, переходимо у вершину . Відмітимо, що ребро  після цих дій вважається переглянутим і називається ребром дерева, а вершина  називається батьківською по відношенню до вершини .

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

Пошук в глибину в неорієнтованому графі

У загальному випадку, коли ми перейшли в будь-яку вершину графа, в нашому випадку це вершина , виникають два варіанти можливих дій:

Читати повністю