Поиск в графе 2
.pdf
Задача поиска в графе |
Поиск в глубину |
|
|
Свойства поиска в глубину
Отметим, следующее очевидное свойство поиска в глубину Замечание 1
1) Чем раньше вершина попала в очередь Stack, тем меньше е¼ номер num.
Или, что то же самое: чем ближе вершина к голове стека тем больше е¼ номер num.
2) Åñëè v находится в стеке, то все вершины стека, расположенные ближе к голове стека чем v будут потомками v в дереве поиска
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойства поиска в глубину
Отметим, следующее очевидное свойство поиска в глубину Замечание 1
1) Чем раньше вершина попала в очередь Stack, тем меньше е¼ номер num.
Или, что то же самое: чем ближе вершина к голове стека тем больше е¼ номер num.
2) Åñëè v находится в стеке, то все вершины стека, расположенные ближе к голове стека чем v будут потомками v в дереве поиска
Далее этими свойствами мы будем пользоваться без ссылок на замечание
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
Напомним, что ребро, которое не принадлежит дереву поиска называется обратным
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
Напомним, что ребро, которое не принадлежит дереву поиска называется обратным
Чтобы прояснить смысл этого названия обратимся к дереву поиска, которое получилось в рассмотренном выше примере работы алгоритма
v1 |
|
|
v2 |
v5 |
v7 |
v3 |
v8 |
|
|
v6 v9 |
|
v4 |
|
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
Напомним, что ребро, которое не принадлежит дереву поиска называется обратным
Чтобы прояснить смысл этого названия обратимся к дереву поиска, которое получилось в рассмотренном выше примере работы алгоритма
v1 |
|
v7 |
|
Напомним, что древесные ребра показаны |
|
|
|||
v2 |
|
|
||
v5 |
v8 |
сплошной линией |
||
v3 |
|
|
||
|
|
v9 |
|
|
v4 |
|
v6 |
|
|
|
|
|
|
|
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
Напомним, что ребро, которое не принадлежит дереву поиска называется обратным
Чтобы прояснить смысл этого названия обратимся к дереву поиска, которое получилось в рассмотренном выше примере работы алгоритма
v1 |
|
v7 |
|
Напомним, что древесные ребра показаны |
|
|
|||
v2 |
|
|
||
v5 |
|
сплошной линией |
||
v3 |
v8 |
|
обратные штриховкой |
|
|
v6 v9 |
|
|
|
v4 |
|
|
|
|
|
|
|
|
|
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
Напомним, что ребро, которое не принадлежит дереву поиска называется обратным
Чтобы прояснить смысл этого названия обратимся к дереву поиска, которое получилось в рассмотренном выше примере работы алгоритма
v1 |
|
v7 |
|
Напомним, что древесные ребра показаны |
|
|
|||
v2 |
|
|
||
v5 |
|
сплошной линией |
||
v3 |
v8 |
|
обратные штриховкой |
|
|
v6 v9 |
|
Видно, что обратные ребра идут снизу-вверх |
|
v4 |
|
|
(соединяют предка с потомком) |
|
|
|
|
|
|
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
Напомним, что ребро, которое не принадлежит дереву поиска называется обратным
Чтобы прояснить смысл этого названия обратимся к дереву поиска, которое получилось в рассмотренном выше примере работы алгоритма
v1 |
|
v7 |
|
Напомним, что древесные ребра показаны |
|
|
|||
v2 |
|
|
||
v5 |
|
сплошной линией |
||
v3 |
v8 |
|
обратные штриховкой |
|
|
v6 v9 |
|
Видно, что обратные ребра идут снизу-вверх |
|
v4 |
|
|
(соединяют предка с потомком) |
|
|
|
|
|
|
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
v1 |
|
|
v2 |
v5 |
v7 |
v3 |
v8 |
|
|
v6 v9 |
|
v4 |
|
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
v1 |
|
|
v2 |
v5 |
v7 |
v3 |
v8 |
|
|
v6 v9 |
|
v4 |
|
Принято говорить снизу-вверх, а не сверху-вниз, поскольку обратное ребро в первый раз обнаруживается из потомка
Расин О.В. |
Поиск в графе |
|
|