Олександр Рудик

Пошук і перебір
остовних (каркасних) дерев

(Інформатика та інформаційні технології в навчальних закладах, 2008, № 5, с. 102–104)

Означення 1. Запровадимо такі поняття:

  1. Підграф G'(V', E') графа G(V, E) називають остовним (каркасним), якщо V' = V, тобто множини вершин графа G і підграфа G' збігаються.

  2. Остовним (каркасним) деревом графа називають його довільний остовний (каркасний) підграф, що є деревом.

      Ідея методу пошуку у ширину полягає у виборі кореня дерева й послідовному визначенні вершин дерева, які можна досягнути з кореня, пройшовши одне ребро, два ребра, три ребра ... Таку кількість ребер називають рівнем вершин. Позначимо через V T множину вершин дерева T, через E T — множину ребер дерева T, через дерева L(v) — рівень вершини v.

Алгоритм пошуку в ширину

  1. Вибираємо вершину v0 початкового графа. Надаємо величин: L(v0) = 0; V T = {v0}; l = 0.

  2. Вибираємо вершину vl з множини V T, при якій L(vl) = l.

  3. Вибираємо вершину v з різниці множин V \ V T, що суміжна (тобто сполучена ребром) з vl долучаємо:

    • вершину v до множини V T;
    • ребро (vl; v) до множини E T

    і надаємо величину: L(v) = l + 1.

  4. Крок 3 здійснюємо доти, поки не буде розглянуто всі вершини з V \ V T, що постійно змінюється.

  5. Кроки 2–4 здійснюємо доти, поки не переберемо всі вершни vl з множини V T, при яких L(vl) = l.

  6. Збільшуємо величину l на 1.

  7. Кроки 2–6 здійснюємо до споравдження рівності V = V T.

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

Алгоритм пошуку у глибину

  1. Усі вершини графа мітимо як «нова».

  2. Вибираємо вершину v0 початкового графа, яка буде коренем дерева. Замінюємо її мітку на «використана». Надаємо величину: v = v0.

  3. Якщо є вершини w, що суміжні (сполучені ребром) з вершиною v і мають мітку «нова», виконаємо такі дії:

    • вибираємо одну з такик вершин w і замінюємо її мітку на «використана»;

    • надаємо величину v = w і знову починаємо виконання пункту 3.

  4. Якщо вершина v відмінна від v0, замінюємо поточну величину v на її безпосереднього предка і повторюємо виконання кроку 3.

Зауваження 1. Для перебору всіх можливих дерев за допомогою викладених методів на кроці 3 обох алгоритмів маємо передбачити перебір усіх можливих множин вершин і відповідних ребер, які можливо долучити на цьому кроці.