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