На главную   ::   Содержание



Алгоритмы обхода деревьев и графов

Предположим, что есть бинарное дерево. Каждый узел имеет следующую структуру:

$\displaystyle \begin{array}{l}
$Struct TNode$: \\
\quad left,\; right\\
\quad key \\
\end{array}
$

где $ left$ и $ right$ -- соответственно левый и правый потомок (если потомка нет, значения равны NULL), $ Key$ -- значение ключа. Пусть мы хотим выписать все значения ключей в узлах дерева. Нужно его обойти. Пусть корень дерева будет $ root$. Обход дерева выполняется рекурсивной процедурой STEP$ (root)$:

24pt STEP

24pt
1
if $ x.left\neq$NULL then STEP$ (x.left)$
2
write(x.key)
3
if $ x.right\neq$NULL then STEP$ (x.right)$

Можно как угодно менять местами строки программы -- будут получаться разные порядки обхода (прямой, обратный, «корень -- левый ребенок -- правый ребенок» и так далее).

Граф (пара множеств $ V$ -- вершины (узлы), $ E$ - ребра (дуги) и функция $ T: E\rightarrow V\times V$. $ \forall  e\in E$ $ T(e)=(u,v)$, где $ u$ -- начало дуги, а $ v$ -- конец) можно обойти в ширину или в глубину (есть и другие варианты, например обход в ширину с приоритетами (как в алгоритме Дейкстры)).

Обход в глубину (DFS -- Depth-First-Search). Начинается с некоторой вершины $ u\in V$. Вершина помечается как обработанная и выполняется переход в любую другую непомеченную вершину $ v$, инцидентную с $ u$ (то есть переходим по дуге $ (u,v)\in E$. Если переход сделать нельзя, возвращаемся, откуда пришли). Пусть в программе $ was[1..n]$ -- массив пометок. Ноль -- вершина не обработана, один -- обработана (сначала весь массив забит нулями). Вызов функции DFS$ (u)$ обойдет одну компоненту связности к которой вершина $ u$ принадлежит. Чтобы обойти весь граф, нужно вызвать DFS от каждой вершины графа:

24pt TRY

24pt
1
$ was\leftarrow \mathbb{O}$
2
for $ u\in V$ do if was[u]=0 then DFS$ (u)$

Сам обход от одной вершины:

24pt DFS

24pt
1
was[u]=1
2
write($ u$)
3
for $ v\in V: \exists (u,v)\in E:  was[v]=0$ do DFS$ (v)$

Функция TRY$ (G)$, вызванная для графа $ G$, выведет вершины в порядке обхода в глубину. Можно вывести обратный порядок обхода в глубину (прямая топологическая сортировка получится, которая существует, если в графе нет циклов) если write($ u$) написать после $ 3$-й строки. (Обратная топологическая сортрировка может быть получена только если перевернуть прямую).

Обход в ширину (BFS -- Breadth-First-Search). Для каждой вершины $ u\in V$ есть пометка $ was[u]$ -- была ли вершина в очереди на обработку. В очередь заносится одна вершина (с которой начинаем). Пусть это вершина $ u$. Полагается $ was[u]=1$. До тех пор, пока очередь не пуста, выполняется следующее. Из очереди берется очередная вершина $ u$. В очередь заносятся все те вершины $ v$, в которые можно добраться из $ u$ и при этом для них $ was[v]=0$. Для всех этих вершин $ v$ ставится пометка $ was[v]=1$. (В программе заведем очередь $ X$)

24pt BFS

24pt
1
$ was[u]\leftarrow 1$
2
PUSH$ (X,u)$
3
while Очередь не пуста do
4
$ u\leftarrow$POP$ (X)$
5
write($ u$)
6
for $ v\in V: \exists (u,v)\in E:  was[v]=0$ do
7
$ was[v]\leftarrow 1$
8
PUSH$ (X,v)$

Нужно переписать алгоритм TRY$ (G)$, чтобы он выполнял обход всего графа в ширину.

Дерево -- тоже граф. Поэтому его тоже можно обойти в ширину (до этого мы обходили только в глубину, причем в строгом порядке).



На главную   ::   Содержание