Презентация на тему: Метод поиска в глубину

Метод поиска в глубину
Поиск в глубину ( Depth-first search, DFS )
Процедура Поиск( u)
Процедура Поиск_в_графе
Анализ
Поиск в глубину в неориентированном графе
Глубинный остовный лес
Свойства поиска в глубину
Теорема
Поиск в глубину в ориентированном графе
Метод поиска в глубину
Решение задачи топологической сортировки методом поиска в глубину
Пример
Поиск компонент связности в графе
1/14
Средняя оценка: 4.3/5 (всего оценок: 33)
Код скопирован в буфер обмена
Скачать (91 Кб)
1

Первый слайд презентации: Метод поиска в глубину

Лекция 8

Изображение слайда
2

Слайд 2: Поиск в глубину ( Depth-first search, DFS )

Пусть задан граф G = ( V, E ). Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все непройденные смежные вершины и повторить поиск для них. Пусть в начальный момент времени все вершины окрашены в белый цвет. Из множества всех белых вершин выберем любую вершину : v 1. Выполним для нее процедуру Поиск( v 1). Перекрасим ее в черный цвет. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Изображение слайда
3

Слайд 3: Процедура Поиск( u)

Поиск ( u ) { цвет [ u ] ← серый; d[u] = time++; // время входа в вершину, // порядковый глубинный номер вершины для  v  смежные ( u ) выполнить {     если (цвет [v] = белый) то { отец [v] ← u; Поиск( v ) ; } } цвет [ u ] ← чёрный; f [u] ← time++; // время выхода из вершины }

Изображение слайда
4

Слайд 4: Процедура Поиск в графе

Поиск_в_графе () { для  u  V выполнить {    цвет [u] ← белый ; отец [u]← NULL; } time ← 0; для  u  V выполнить если (цвет [u] = белый) то Поиск( u ) ; }

Изображение слайда
5

Слайд 5: Анализ

Общее число операций при выполнении Поиск_в_графе : O(|V|) Общее число операций при выполнении Поиск( u ) : Цикл выполняется | смежные [v]| раз. ∑ | смежные [v]| = O(|E|) Общее число операций : O(|V|+|E|)

Изображение слайда
6

Слайд 6: Поиск в глубину в неориентированном графе

2 3 1 5 4 6

Изображение слайда
7

Слайд 7: Глубинный остовный лес

Поиск в глубину на неориентированном графе G = ( V, Е ) разбивает ребра, составляющие Е, на два множества Т и В. Ребро ( v, w ) помещается в множество Т, если узел w не посещался до того момента, когда мы, рассматривая ребро (и, w ), оказались в узле v. В противном случае ребро ( v, w ) помещается в множество В. Ребра из Т будем называть древесными, а из В — обратными. Подграф (V, Т) представляет собой неориентированный лес, называемый остовным лесом для G, построенным поиском в глубину, или, короче, глубинным остовным лесом для G. Если этот лес состоит из единственного дерева, (V, Т) будем называть по аналогии глубинным остовным деревом. Заметим, что если граф связен, то глубинный остовный лес будет деревом. Узел, с которого начинался поиск, считается корнем соответствующего дерева.

Изображение слайда
8

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

Времена обнаружения и окончания обработки вершин образуют правильную скобочную структуру. 1 2 3 4 5 6 7 8 9 10 ( s(z(y(x x)y )( w w) z) s) Z w S x y

Изображение слайда
9

Слайд 9: Теорема

При поиске в глубину в графе G = ( V, E ) для любых двух вершин u и v выполняется одно из следующих утверждений : Отрезки [d[ u ],f[ u ]] и [d[ v ],f[ v ]] не пересекаются. Отрезок [d[ u ],f[ u ]] целиком содержится внутри отрезка [d[ v ],f[ v ]] и u есть потомок v в дереве поиска в глубину. Отрезок [d[ v ],f[ v ]] целиком содержится внутри отрезка [d[ u ],f[ u ]] и v есть потомок u в дереве поиска в глубину.

Изображение слайда
10

Слайд 10: Поиск в глубину в ориентированном графе

v 2 v 5 v 1 v 7 v 6 v 3 v 4 v 8

Изображение слайда
11

Слайд 11

Поиск в глубину в ориентированном графе G разбивает множество его ребер на четыре класса. 1) Древесные ребра, идущие к новым узлам в процессе поиска. 2) Прямые ребра, идущие от предков к подлинным потомкам, но не являющиеся древесными ребрами. 3) Обратные ребра, идущие от потомков к предкам (возможно, из узла в себя). 4) Поперечные ребра, соединяющие узлы, которые не являются ни предками, ни потомками друг друга.

Изображение слайда
12

Слайд 12: Решение задачи топологической сортировки методом поиска в глубину

Топологическая_сортировка ( u ) { цвет [ u ] ← серый; для  v  смежные ( u ) выполнить {     если (цвет [v] = белый) то { Топологическая_сортировка( v ) ; } } цвет [ u ] ← чёрный; Поместить u в начало списка ; }

Изображение слайда
13

Слайд 13: Пример

Трусы Носки Штаны Ремень Ботинки Рубашка Галстук Пиджак Часы Пиджак Ремень Ботинки Штаны Трусы Носки Галстук Рубашка Часы

Изображение слайда
14

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

Поиск ( u, n ) { цвет [ u ] ← серый; C[u] ← n; // номер компоненты связности для  v  смежные ( u ) выполнить {     если (цвет [v] = белый) то Поиск( v, n ) ; } цвет [ u ] ← чёрный; } Поиск_в_графе () { для  u  V выполн и ть цвет [u] ← белый ; nk ← 0; для  u  V выполнить если (цвет [u] = белый) то { nk ++; Поиск( u, nk ) ; } }

Изображение слайда