Дискретная математика (Обход графа, Алгоритм Форда – Фалкерсона и т.д. и т.п)

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

Описание алгоритма

Пусть нам необходимо обойти граф G (V, E), который представлен списком смежности Г. Обход графа подразумевает некоторое систематическое перечисление его вершин. Для этого используются следующие вспомогательные структуры данных:

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

Стек – это структура данных, в которой первый помещенный в нее элемент извлекается последним. Очередь – это структура данных, в которой первый помещенный в нее элемент извлекается первым.

Массив X, длина которого равна числу вершин, содержит данные о том, была ли отмечена (пройдена) вершина. Каждый элемент массива соответствует одной вершине графа и может принимать два значения:

1 – вершина отмечена (пройдена);

0 – вершина не отмечена.

Рассмотрим, как осуществляется обход поэтапно:

1. Обнуление массива X. До начала обхода все вершины являются неотмеченными.

2. Выбирается некоторая произвольная вершина v, с которой будет начинаться обход.

3. Вершина v помещается в структуру Т и отмечается в массиве Х как пройденная (X [v] := 1).

4. Из структуры T извлекается вершина (обозначим её u). Эта вершина является пройденной. Таким образом, именно на этом этапе мы выделяем обойденные вершины.

5. По списку смежности Г поочередно выбираются все вершины смежные с v (обозначим вершину смежную с v – w) и если они не были раннее отмечены (то есть, если X [w] = 0), то они помещаются в структуру Т и отмечаются.

Если в структуре T находятся какие-либо вершины, то осуществляется переход к п. 4. Если же нет, то обход графа G (V, E) закончен.

Пример

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

Рассмотрим на примере обход графа G (V, E) (рис. 1).

Рис. 1	Список смежности ( Г )
	1 – 2, 4 2 – 1, 3, 4 3 – 2, 4 4 – 1, 2, 3

1. Обнулим массив X.

X:	1	2	3	4
	0	0	0	0

1. Начнем обход с первой вершины (v = 1).

2. Поместим вершину 1 (v = 1) в структуру T и отметим ее в массиве X как пройденную.

T: 1	X: 1 2 3 4 1 0 0 0

1. Извлекаем из структуры T вершину 1 (v = 1), т.е. вершина 1 пройдена.

T:

1. Затем помещаем вершины, смежные с первой (v = 1) и еще не отмеченные в массиве X, в структуру T и отмечаем их в массиве X.

T: 2 4

X: 1 2 3 4 1 1 0 1

1. Извлекаем из структуры T вершину 4 (v = 4), т.е. вершина 4 пройдена.

T:

2

1. Затем помещаем вершины, смежные с четвертой (v = 4) и еще не отмеченные в массиве X (v = 2 и v = 3), в структуру T и отмечаем их в массиве X.

T: 2 3

X: 1 2 3 4 1 1 1 1

1. Извлекаем из структуры T вершину 3 (v = 3), т.е. вершина 3 пройдена.

T:

2

1. Все вершины, смежные с третьей, уже отмечены в массиве X, поэтому ничего не помещаем в структуру T.

2. Извлекаем из структуры T вершину 2 (v = 2), т.е. вершина 2 пройдена.

T:

1. Все вершины, смежные со второй, уже отмечены в массиве X, поэтому ничего не помещаем в структуру T.

2. Структура T пуста. Обход вершин графа закончен: 1 – 4 – 3 – 2.

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

Рассмотрим на примере обход графа G (V, E) (рис. 2).

Рис. 2	Список смежности ( Г )
	1 – 2, 4 2 – 1, 3, 4 3 – 2, 4 4 – 1, 2, 3

1. Обнулим массив X.

X:	1	2	3	4
	0	0	0	0

1. Начнем обход с первой вершины (v = 1).

2. Поместим вершину 1 (v = 1) в структуру T и отметим ее в массиве X как пройденную.

   T: 1	X: 1 2 3 4 1 0 0 0

3. Извлекаем из структуры T вершину 1 (v = 1), т.е. вершина 1 пройдена.

T:

1. Затем помещаем вершины, смежные с первой (v = 1) и еще не отмеченные в массиве X, в структуру T и отмечаем их в массиве X.

   T: 2 4

   X: 1 2 3 4 1 1 0 1

2. Извлекаем из структуры T вершину 2 (v = 2), т.е. вершина 2 пройдена.

T:

4

1. Затем помещаем вершины, смежные со второй (v = 2) и еще не отмеченные в массиве X (v = 3), в структуру T и отмечаем их в массиве X.

   T: 4 3

   X: 1 2 3 4 1 1 1 1

2. Извлекаем из структуры T вершину 4 (v = 4), т.е. вершина 4 пройдена.

   T:

   3

3. Все вершины, смежные с четвертой, уже отмечены в массиве X, поэтому ничего не помещаем в структуру T.

4. Извлекаем из структуры T вершину 3 (v = 3), т.е. вершина 3 пройдена.

T:

1. Все вершины, смежные с третьей, уже отмечены в массиве X, поэтому ничего не помещаем в структуру T.

2. Структура T пуста. Обход вершин графа закончен: 1 – 2 – 4 – 3.

На практике обход в глубину можно использовать, в частности, для получения ориентированного дерева из неориентированного. Рассмотрим это на примере.

Пример получения ориентированного дерева

Исходное дерево представлено на рис. 3. Наша цель – посредством обхода исходного дерева в глубину получить ориентированное дерево с корнем v и списком смежности Г’.

Рис. 3	Список смежности ( Г )
	1 – 2, 3 2 – 1, 4, 5 3 – 1 4 – 2 5 – 2, 6, 7, 8 6 – 5 7 – 5 8 – 5

1. Обнулим массив X.

X:	1	2	3	4	5	6	7	8
	0	0	0	0	0	0	0	0

1. Пусть корнем будет вершина 5 (v = 5). Поместим вершину 5 в структуру T и пометим ее как пройденную в массиве Х.

T:

5

X:	1	2	3	4	5	6	7	8
	0	0	0	0	1	0	0	0

1. Затем извлекаем из структуры Т вершину 5 (v = 5) и помещаем смежные с ней вершины (ранее не пройденные) в Т, отметим их в массиве X.

T:

2

6

7

8