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

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

Временная сложность поиска в ширину

Лемма 1.1

Алгоритм поиска в ширину просматривает каждую запись списка смежности однократно

Нетрудно увидеть, что после чтения очередной записи, мы либо включаем соответствующую вершину в очередь (если вершина еще не посещалась)

или игнорируем ее (если вершина уже была посещена из другой вершины)

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

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

Временная сложность поиска в ширину

Лемма 1.1

Алгоритм поиска в ширину просматривает каждую запись списка смежности однократно

Нетрудно увидеть, что после чтения очередной записи, мы либо включаем соответствующую вершину в очередь (если вершина еще не посещалась)

или игнорируем ее (если вершина уже была посещена из другой вершины)

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

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

Временная сложность поиска в ширину

Теорема 1.1

Пусть G = (V;E) связный (n;m)-граф. Тогда алгоритм поиска в ширину требует O(n + m) операций.

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

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

Временная сложность поиска в ширину

Теорема 1.1

Пусть G = (V;E) связный (n;m)-граф. Тогда алгоритм поиска в ширину требует O(n + m) операций.

Д о к а з а т е л ь с т в о. Поскольку список смежности содержит 2m записей, то его чтение требует 2m операций.

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

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

Временная сложность поиска в ширину

Теорема 1.1

Пусть G = (V;E) связный (n;m)-граф. Тогда алгоритм поиска в ширину требует O(n + m) операций.

Д о к а з а т е л ь с т в о. Поскольку список смежности содержит 2m записей, то его чтение требует 2m операций.

Конечно нужно учитывать еще манипуляции, связанные с вставкой/извлечением вершины из очереди,

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

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

Временная сложность поиска в ширину

Теорема 1.1

Пусть G = (V;E) связный (n;m)-граф. Тогда алгоритм поиска в ширину требует O(n + m) операций.

Д о к а з а т е л ь с т в о. Поскольку список смежности содержит 2m записей, то его чтение требует 2m операций.

Конечно нужно учитывать еще манипуляции, связанные с вставкой/извлечением вершины из очереди, но они увеличивают число действий в постоянное число раз,

поэтому сложность не более c m, где c некоторая константа.

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

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

Временная сложность поиска в ширину

Теорема 1.1

Пусть G = (V;E) связный (n;m)-граф. Тогда алгоритм поиска в ширину требует O(n + m) операций.

Д о к а з а т е л ь с т в о. Поскольку список смежности содержит 2m записей, то его чтение требует 2m операций.

Конечно нужно учитывать еще манипуляции, связанные с вставкой/извлечением вершины из очереди, но они увеличивают число действий в постоянное число раз,

поэтому сложность не более c m, где c некоторая константа. Последнее и означает, что сложность O(n + m) (n необходимо если m < n)

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

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

Временная сложность поиска в ширину

Теорема 1.1

Пусть G = (V;E) связный (n;m)-граф. Тогда алгоритм поиска в ширину требует O(n + m) операций.

Д о к а з а т е л ь с т в о. Поскольку список смежности содержит 2m записей, то его чтение требует 2m операций.

Конечно нужно учитывать еще манипуляции, связанные с вставкой/извлечением вершины из очереди, но они увеличивают число действий в постоянное число раз,

поэтому сложность не более c m, где c некоторая константа. Последнее и означает, что сложность O(n + m) (n необходимо если m < n)

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

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

Некоторые простые модификации поиска в ширину

Иногда в приложениях требуется выделить все поперечные ребра, чтобы это сделать нужно

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

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

Некоторые простые модификации поиска в ширину

Иногда в приложениях требуется выделить все поперечные ребра, чтобы это сделать нужно

в п. 3 не игнорировать уже посещенную вершину u, а 1)проверить

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