Алгоритмы прохождения графа.

Алгоритм прохождения может быть использован как алгоритм поиска, если узлами графа являются элементы таблицы.

Имеем граф G = (X, U), X = {x₁, x₂,…, x_n}. Каждое прохождение можно рассматривать как определенную последовательность. Максимальное число прохождений (перестановок) – n!.

Алгоритм прохождения графа в глубину:

Цифры на ребрах графа обозначают шаги посещения. Будем различать посещаемые ( ) и не посещаемые ( - - ) вершины. Каждая вершина обходится два раза. Если все смежные вершины пройдены, то происходит откат в предыдущую вершину. В том случае, если из текущей вершины все соседние вершины пройдены, то осуществляем возврат к той вершине, откуда был осуществлен переход к текущей.

Определимсписки смежности для каждой вершины графа G:

1:2, 3, 5 2:1, 3, 4 3:1, 2, 4, 5 4: 2, 3 5: 1,3

t: 1, 2, 3, 4, 5

Если граф G связный, то описанный процесс определяет прохождение (обход) графа G. Если же граф G не связный, то проходим только одну из компонент графа G, которая содержит начальную вершину. Если граф G является несвязным, то для получения полного обхода необходимо получать этот процесс в каждой связной компоненте. С помощью этого метода можно определить количество компонент.

Для каждого выбора начальной вершины в связном графе может быть получено единственное прохождение. Если граф представляет собой объединение компонент: и | x _i | = n _i , то количество прохождений такого несвязного графа: n ₁ × n ₂ × … × n _р ( i = 1, 2,…, p).

Пусть граф G = (X, U) задан структурой смежности < М(x ₁), М(x ₂),…, М(x _n)>. Определим Num(x) как массив для регистрации посещений вершин (Num(x)=1, если вершина не посещалась; Num(x)=0, если вершина посещалась). Тогда алгоритм прохождения графа в глубину будет выглядеть так:

" x Î X выполнить Num(x)=1;

" x Î X выполнить: если Num(x)=1, то D(x);

Процедура D(x);

начало

R(V);

Num(V)=0;

" t Î M(V) выполнить: если Num(t)=1, то D(t);

конец;

Алгоритм прохождения графа в ширину:

Определимсписки смежности для каждой вершины графа G:

1:2, 3, 5 2:1, 3, 4 3:1, 2, 4, 5 4: 2, 3 5: 1,3

t: 1, 2, 3, 4, 5 (для выбранной вершины переписываем весь список смежности).

Выберем начальную вершину x _н. Первые элементы искомой перестановки t являются элементами смежного списка вершины x _н, т.е. M(x _н). Обозначим список смежности следующим образом: M(x _н) = {(w₁, x_н), (w₂, x_н),…,(w_k, x_н)}. Следующими элементами перестановки будут те элементы их M(w₁), которые отсутствуют в формируемой перестановке t. Затем, берем все элементы из M(w₂), и т.д. обход прекращается, когда все вершины, достижимые из x _н, будут содержаться в t (w_i Î X, i=1, 2,…, k).