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

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

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

Мы сформулировали алгоритм в предположении, что граф связен (это было сделано для упрощения обозначений )

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

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

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

Мы сформулировали алгоритм в предположении, что граф связен (это было сделано для упрощения обозначений ) Однако его нетрудно модифицировать для случая несвязного графа

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

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

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

Мы сформулировали алгоритм в предположении, что граф связен (это было сделано для упрощения обозначений ) Однако его нетрудно модифицировать для случая несвязного графа

После того, как стек Stack стал пустым проверить: не осталось ли вершин графа v, которые еще не посещены

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

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

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

Мы сформулировали алгоритм в предположении, что граф связен (это было сделано для упрощения обозначений ) Однако его нетрудно модифицировать для случая несвязного графа

После того, как стек Stack стал пустым проверить: не осталось ли вершин графа v, которые еще не посещены

если таковые есть, то запустить алгоритм из такой вершины

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

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

Модификация поиска в глубину

Теорема 1.2

Алгоритм поиска в глубину позволяет установить является ли граф G = (V; E) связным.

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

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

Модификация поиска в глубину

Теорема 1.2

Алгоритм поиска в глубину позволяет установить является ли граф G = (V; E) связным. Более того он позволяет найти все

компоненты связности графа G = (V; E).

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

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

Модификация поиска в глубину

Теорема 1.2

Алгоритм поиска в глубину позволяет установить является ли граф G = (V; E) связным. Более того он позволяет найти все

компоненты связности графа G = (V; E).

Новая компонента появляется тогда, когда мы возобновляем поиск после того, как Stack становится пустым.

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

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

Свойства поиска в глубину

Отметим, следующее очевидное свойство поиска в глубину

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

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

Свойства поиска в глубину

Отметим, следующее очевидное свойство поиска в глубину Замечание 1

1) Чем раньше вершина попала в очередь Stack, тем меньше е¼ номер num.

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

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

Свойства поиска в глубину

Отметим, следующее очевидное свойство поиска в глубину Замечание 1

1) Чем раньше вершина попала в очередь Stack, тем меньше е¼ номер num.

Или, что то же самое: чем ближе вершина к голове стека тем больше е¼ номер num.

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