Поиск в графе 1
.pdf
Задача поиска в графе |
Поиск в ширину |
|
|
Поиск в графе
Расин О.В.
28 марта 2015 г.
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Задача поиска в графе
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Задача поиска в графе состоит в обходе всех вершин графа.
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Задача поиска в графе состоит в обходе всех вершин графа.
При этом для эффективности поиска необходимо, чтобы каждая вершина графа просматривалась как можно меньшее число раз.
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Задача поиска в графе состоит в обходе всех вершин графа.
При этом для эффективности поиска необходимо, чтобы каждая вершина графа просматривалась как можно меньшее число раз.
Как мы увидим, можно добиться однократного прохождения каждой вершины.
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Задача поиска в графе состоит в обходе всех вершин графа.
При этом для эффективности поиска необходимо, чтобы каждая вершина графа просматривалась как можно меньшее число раз.
Как мы увидим, можно добиться однократного прохождения каждой вершины.
Наиболее распространенными методами поиска являются поиск в глубину è поиск в ширину. Мы рассмотрим каждый из этих методов.
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Задача поиска в графе состоит в обходе всех вершин графа.
При этом для эффективности поиска необходимо, чтобы каждая вершина графа просматривалась как можно меньшее число раз.
Как мы увидим, можно добиться однократного прохождения каждой вершины.
Наиболее распространенными методами поиска являются поиск в глубину è поиск в ширину. Мы рассмотрим каждый из этих методов.
Заметим, что каждый из этих алгоритмов является базовым и, часто они используются в качестве вспомогательных (иногда неявно) в практических приложениях
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Задача поиска в графе состоит в обходе всех вершин графа.
При этом для эффективности поиска необходимо, чтобы каждая вершина графа просматривалась как можно меньшее число раз.
Как мы увидим, можно добиться однократного прохождения каждой вершины.
Наиболее распространенными методами поиска являются поиск в глубину è поиск в ширину. Мы рассмотрим каждый из этих методов.
Заметим, что каждый из этих алгоритмов является базовым и, часто они используются в качестве вспомогательных (иногда неявно) в практических приложениях
Какой из этих алгоритмов поиска использовать зависит от свойств конкретной задачи
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Некоторые договоренности
Для упрощения обозначений будем предполагать, что
граф G = (V G;EG) связный
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в ширину |
|
|
Некоторые договоренности
Для упрощения обозначений будем предполагать, что
граф G = (V G;EG) связный
через n обозначается число вершин в графе, а через m число ребер
Расин О.В. |
Поиск в графе |
|
|