Поиск в графе 1

Задача поиска в графе	Поиск в ширину

Формулировка алгоритма

3. Берем очередную вершину v из очереди

(v := Front:GetHead()) и просматриваем ее список смежности. Для каждого соседа u вершины v если Visit[u] = 0, то

Front:Add(u); Visit[u] := 1; Father[u] := v,

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Формулировка алгоритма

3. Берем очередную вершину v из очереди

(v := Front:GetHead()) и просматриваем ее список смежности. Для каждого соседа u вершины v если Visit[u] = 0, то

Front:Add(u); Visit[u] := 1; Father[u] := v, num[u] := counterNum,

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Формулировка алгоритма

3. Берем очередную вершину v из очереди

(v := Front:GetHead()) и просматриваем ее список смежности. Для каждого соседа u вершины v если Visit[u] = 0, то

Front:Add(u); Visit[u] := 1; Father[u] := v, num[u] := counterNum, counterNum + +

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Формулировка алгоритма

3. Берем очередную вершину v из очереди

(v := Front:GetHead()) и просматриваем ее список смежности. Для каждого соседа u вершины v если Visit[u] = 0, то

Front:Add(u); Visit[u] := 1; Father[u] := v, num[u] := counterNum, counterNum + +

Если Visit[u] = true, то не производим с u никаких действий

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Формулировка алгоритма

3. Берем очередную вершину v из очереди

(v := Front:GetHead()) и просматриваем ее список смежности. Для каждого соседа u вершины v если Visit[u] = 0, то

Front:Add(u); Visit[u] := 1; Father[u] := v, num[u] := counterNum, counterNum + +

Если Visit[u] = true, то не производим с u никаких действий

Перейти к шагу 2.

4. Все вершины графа просмотрены, и алгоритм заканчивает работу.

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Пример работы алгоритма

v1	v3	v6	v7
			Рассмотрим граф на рис.
v2	v4	v5
v8		v9

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Пример работы алгоритма

v1	v3	v6	v7
v2	v4	v5
v8		v9

Рассмотрим граф на рис.

вершины в списке смежности упорядочены по возрастанию индекса

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Пример работы алгоритма

v1	v3	v6	v7
v2	v4	v5
v8		v9

Рассмотрим граф на рис.

вершины в списке смежности упорядочены по возрастанию индекса

в качестве начальной вершины поиска возьмем v1

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Пример работы алгоритма

v1	v3	v6	v7
v2	v4	v5
v8		v9

Рассмотрим граф на рис.

вершины в списке смежности упорядочены по возрастанию индекса

в качестве начальной вершины поиска возьмем v1

Далее показаны последовательные итерации цикла в пп. 2-3.

Расин О.В.	Поиск в графе

Задача поиска в графе	Поиск в ширину

Пример работы алгоритма

v1	v3	v6	v7
v2	v4	v5
v8		v9

Рассмотрим граф на рис.

вершины в списке смежности упорядочены по возрастанию индекса

в качестве начальной вершины поиска возьмем v1

Далее показаны последовательные итерации цикла в пп. 2-3. Древесные ребра и вершины показаны в виде дерева.

Расин О.В.	Поиск в графе