Поиск в графе 2
.pdf
Задача поиска в графе |
Поиск в глубину |
|
|
Пример работы алгоритма
v4 |
v1 |
v3 |
v2 |
|
v5 v6
v8 v9
v7 |
Рассмотрим граф на рис.
вершины в списке смежности упорядочены по возрастанию индекса
в качестве начальной вершины поиска возьмем v1
Далее показаны последовательные итерации цикла в пп. 2-3.
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Пример работы алгоритма
v4 |
v1 |
v3 |
v2 |
|
v5 v6
v8 v9
v7 |
Рассмотрим граф на рис.
вершины в списке смежности упорядочены по возрастанию индекса
в качестве начальной вершины поиска возьмем v1
Далее показаны последовательные итерации цикла в пп. 2-3. Древесные ребра и вершины показаны в виде дерева.
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Пример работы алгоритма
v4 |
v1 |
v3 |
v2 |
|
v5 v6
v8 v9
v7 |
Рассмотрим граф на рис.
вершины в списке смежности упорядочены по возрастанию индекса
в качестве начальной вершины поиска возьмем v1
Далее показаны последовательные итерации цикла в пп. 2-3. Древесные ребра и вершины показаны в виде дерева. Штриховкой показаны обратные ребра
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Пример работы алгоритма
v4 |
v1 |
v3 |
v2 |
|
v5 v6
v8 v9
v7 |
Рассмотрим граф на рис.
вершины в списке смежности упорядочены по возрастанию индекса
в качестве начальной вершины поиска возьмем v1
Далее показаны последовательные итерации цикла в пп. 2-3. Древесные ребра и вершины показаны в виде дерева. Штриховкой показаны обратные ребра Сбоку от дерева показано
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Пример работы алгоритма
v4 |
v1 |
v3 |
v2 |
|
v5 v6
v8 v9
v7 |
Рассмотрим граф на рис.
вершины в списке смежности упорядочены по возрастанию индекса
в качестве начальной вершины поиска возьмем v1
Далее показаны последовательные итерации цикла в пп. 2-3. Древесные ребра и вершины показаны в виде дерева. Штриховкой показаны обратные ребра
Сбоку от дерева показано состояние стека Stack после завершения данной итерации. 
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Пример работы алгоритма
1) v1 v1
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Пример работы алгоритма
1) v1 v1 |
|
2) |
v1 |
|
|
|
v2 |
||
|
|
v2 |
|
v1 |
|
|
|||
|
|
|
|
|
|
|
v1 |
3) |
v2 |
v3 |
|
||
|
v3 |
v2 |
|
v1 |
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Пример работы алгоритма
1) v1 v1 |
|
2) |
v1 |
|
|
|
v2 |
||
|
|
v2 |
|
v1 |
|
|
|||
|
|
|
|
|
|
|
v1 |
3) |
v2 |
v3 |
|
||
|
v3 |
v2 |
|
v1 |
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Пример работы алгоритма
1) v1 v1 |
|
2) |
v1 |
|
|
|
v2 |
||
|
|
v2 |
|
v1 |
|
|
|||
|
|
|
|
|
|
|
v1 |
3) |
v2 |
v3 |
|
||
|
v3 |
v2 |
|
v1 |
4)
v1
v2 |
|
|
|
|
v4 |
||
v3 |
v3 |
||
v2 |
|||
v4 |
|||
v1 |
|||
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Пример работы алгоритма
1) v1 v1 |
|
2) |
v1 |
|
|
|
v2 |
||
|
|
v2 |
|
v1 |
|
|
|||
|
|
|
|
|
|
|
v1 |
3) |
v2 |
v3 |
|
||
|
v3 |
v2 |
|
v1 |
4) |
v1 |
|
5) |
v1 |
||||
|
||||||||
v2 |
|
|
|
|
|
v2 |
|
|
|
v4 |
|
|
|
|
|
||
v3 |
|
v3 |
|
|
|
v3 |
|
v3 |
|
v2 |
|
|
|
|
v2 |
||
v4 |
|
|
|
|
v4 |
|
||
|
v1 |
|
|
|
|
v1 |
||
|
|
|
|
|
|
|
|
|
Расин О.В. |
Поиск в графе |
|
|