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

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

Модификация поиска в ширину

Теорема 1.2

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

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

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

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

Модификация поиска в ширину

Теорема 1.2

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

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

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

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

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

Свойства поиска в ширину

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

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

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

Свойства поиска в ширину

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

Замечание 1

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

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

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

Свойства поиска в ширину

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

Замечание 1

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

Далее этим свойством мы будем пользоваться без ссылок на замечание

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

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

Свойства поиска в ширину

Пусть G связный граф. Через d(u;v) будем обозначать расстояние (длину кратчайшего пути) между вершинами u и v графа.

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

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

Свойства поиска в ширину

Пусть G связный граф. Через d(u;v) будем обозначать расстояние (длину кратчайшего пути) между вершинами u и v графа.

Уровнем узла u в дереве T называется расстояние от корня до вершины u (обозначается h(u)).

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

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

Свойства поиска в ширину

Пусть G связный граф. Через d(u;v) будем обозначать расстояние (длину кратчайшего пути) между вершинами u и v графа.

Уровнем узла u в дереве T называется расстояние от корня до вершины u (обозначается h(u)). В частности, если v0 корень дерева, то h(v0) = 0.

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

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

Свойства поиска в ширину

Пусть G связный граф. Через d(u;v) будем обозначать расстояние (длину кратчайшего пути) между вершинами u и v графа.

Уровнем узла u в дереве T называется расстояние от корня до вершины u (обозначается h(u)). В частности, если v0 корень дерева, то h(v0) = 0.

Лемма 1.2

(о порядке просмотра вершин и их уровне в дереве поиска) Пусть T дерево поиска в ширину связного графа G

Åñëè num[u] < num[v], то в дереве поиска h(u) 6 h(v)

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

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

Доказательство леммы

Ä î ê à ç à ò å ë ü ñ ò â î.

Пусть w первая вершина, для которой в процессе поиска найдется u, что num[u] < num[v], но h(u) > h(w)

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