Поиск в графе 1
.pdf
Задача поиска в графе |
Поиск в ширину |
|
|
Пример работы алгоритма
|
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 |
|
|
Далее вершины просто удаляются из очереди и ничего не добавляется (т. к. все смежные уже посещены)
после чего алгоритм заканчивает работу
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Древесные и поперечные ребра поиска
Из примера и описания алгоритма видно, что в результате работы алгоритма поиска в ширину получаем дерево, которое называется
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Древесные и поперечные ребра поиска
Из примера и описания алгоритма видно, что в результате работы алгоритма поиска в ширину получаем дерево, которое называется
Ребра графа, вошедшие в дерево поиска называются древесными, остальные поперечными
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Древесные и поперечные ребра поиска
Из примера и описания алгоритма видно, что в результате работы алгоритма поиска в ширину получаем дерево, которое называется
Ребра графа, вошедшие в дерево поиска называются древесными, остальные поперечными
По сути массив Father используется для того, чтобы сохранить дерево поиска в ширину
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Древесные и поперечные ребра поиска
Из примера и описания алгоритма видно, что в результате работы алгоритма поиска в ширину получаем дерево, которое называется
Ребра графа, вошедшие в дерево поиска называются древесными, остальные поперечными
По сути массив Father используется для того, чтобы сохранить дерево поиска в ширину
Из-за произвола в выборе начальной вершины и очередной вершины из списка смежности,
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Древесные и поперечные ребра поиска
Из примера и описания алгоритма видно, что в результате работы алгоритма поиска в ширину получаем дерево, которое называется
Ребра графа, вошедшие в дерево поиска называются древесными, остальные поперечными
По сути массив Father используется для того, чтобы сохранить дерево поиска в ширину
Из-за произвола в выборе начальной вершины и очередной вершины из списка смежности,дерево поиска в ширину не определено однозначно для данного графа
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Древесные и поперечные ребра поиска
Из примера и описания алгоритма видно, что в результате работы алгоритма поиска в ширину получаем дерево, которое называется
Ребра графа, вошедшие в дерево поиска называются древесными, остальные поперечными
По сути массив Father используется для того, чтобы сохранить дерево поиска в ширину
Из-за произвола в выборе начальной вершины и очередной вершины из списка смежности,дерево поиска в ширину не определено однозначно для данного графа (т. е. при разном порядке выбора вершин могут получаться различные деревья)
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Древесные и поперечные ребра поиска
Из примера и описания алгоритма видно, что в результате работы алгоритма поиска в ширину получаем дерево, которое называется
Ребра графа, вошедшие в дерево поиска называются древесными, остальные поперечными
По сути массив Father используется для того, чтобы сохранить дерево поиска в ширину
Из-за произвола в выборе начальной вершины и очередной вершины из списка смежности,дерево поиска в ширину не определено однозначно для данного графа (т. е. при разном порядке выбора вершин могут получаться различные деревья)
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Временная сложность поиска в ширину
Лемма 1.1
Алгоритм поиска в ширину просматривает каждую запись списка смежности однократно
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Временная сложность поиска в ширину
Лемма 1.1
Алгоритм поиска в ширину просматривает каждую запись списка смежности однократно
Нетрудно увидеть, что после чтения очередной записи, мы либо включаем соответствующую вершину в очередь (если вершина еще не посещалась)
Расин О.В. |
Поиск в графе |
|
|