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

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

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

Теорема 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)

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

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

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

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

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

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

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

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

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

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

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

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

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

â ï. ?? не игнорировать уже посещенную вершину u, а 1)проверить : не является ли она отцом вершины v (которая извлечена из очереди) в дереве поиска

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

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

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

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

â ï. ?? не игнорировать уже посещенную вершину u, а 1)проверить : не является ли она отцом вершины v (которая извлечена из очереди) в дереве поиска

2) чтобы не включить ребро в список дважды, то использовать массив num

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

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

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

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

â ï. ?? не игнорировать уже посещенную вершину u, а 1)проверить : не является ли она отцом вершины v (которая извлечена из очереди) в дереве поиска

2) чтобы не включить ребро в список дважды, то использовать массив num

например, договориться, что включаем если num[u] < num[v]

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

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

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

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

â ï. ?? не игнорировать уже посещенную вершину u, а 1)проверить : не является ли она отцом вершины v (которая извлечена из очереди) в дереве поиска

2) чтобы не включить ребро в список дважды, то использовать массив num

например, договориться, что включаем если num[u] < num[v]

(очевидно, когда ребро будет обнаружено вторично, то соотношение между номерами будет противоположно)

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

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

Модификации поиска в глубину на случай несвязного графа

Мы сформулировали алгоритм в предположении, что граф связен

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