Поиск в графе 2
.pdf
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
v1 |
|
|
v2 |
v5 |
v7 |
v3 |
v8 |
|
|
v6 v9 |
|
v4 |
|
Принято говорить снизу-вверх, а не сверху-вниз, поскольку обратное ребро в первый раз обнаруживается из потомка
Если вспомнить порядок просмотра вершин алгоритмом: мы начинали в v1
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
v1 |
|
|
v2 |
v5 |
v7 |
v3 |
v8 |
|
|
v6 v9 |
|
v4 |
|
Принято говорить снизу-вверх, а не сверху-вниз, поскольку обратное ребро в первый раз обнаруживается из потомка
Если вспомнить порядок просмотра вершин алгоритмом: мы начинали в v1 затем перешли в v2
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
v1 |
|
|
v2 |
v5 |
v7 |
v3 |
v8 |
|
|
v6 v9 |
|
v4 |
|
Принято говорить снизу-вверх, а не сверху-вниз, поскольку обратное ребро в первый раз обнаруживается из потомка
Если вспомнить порядок просмотра вершин алгоритмом: мы начинали в v1 затем перешли в v2 затем в v3
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
v1 |
|
|
v2 |
v5 |
v7 |
v3 |
v8 |
|
|
v6 v9 |
|
v4 |
|
Принято говорить снизу-вверх, а не сверху-вниз, поскольку обратное ребро в первый раз обнаруживается из потомка
Если вспомнить порядок просмотра вершин алгоритмом: мы начинали в v1 затем перешли в v2 затем в v3 затем в v4
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
v1 |
|
|
v2 |
v5 |
v7 |
v3 |
v8 |
|
|
v6 v9 |
|
v4 |
|
Принято говорить снизу-вверх, а не сверху-вниз, поскольку обратное ребро в первый раз обнаруживается из потомка
Если вспомнить порядок просмотра вершин алгоритмом: мы начинали в v1 затем перешли в v2 затем в v3 затем в v4
В списке смежности v4 берем запись с v1, обнаруживаем, что v1 посещалась,
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
v1 |
|
|
v2 |
v5 |
v7 |
v3 |
v8 |
|
|
v6 v9 |
|
v4 |
|
Принято говорить снизу-вверх, а не сверху-вниз, поскольку обратное ребро в первый раз обнаруживается из потомка
Если вспомнить порядок просмотра вершин алгоритмом: мы начинали в v1 затем перешли в v2 затем в v3 затем в v4
В списке смежности v4 берем запись с v1, обнаруживаем, что v1 посещалась,
и, значит, найдено обратное ребро v4v1
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
v1 |
|
|
v2 |
v5 |
v7 |
v3 |
v8 |
|
|
v6 v9 |
|
v4 |
|
Принято говорить снизу-вверх, а не сверху-вниз, поскольку обратное ребро в первый раз обнаруживается из потомка
Если вспомнить порядок просмотра вершин алгоритмом: мы начинали в v1 затем перешли в v2 затем в v3 затем в v4
В списке смежности v4 берем запись с v1, обнаруживаем, что v1 посещалась,
и, значит, найдено обратное ребро v4v1
Отметим, что для остальных трех обратных ребер имеет место аналогичная ситуация
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
Лемма 1.2
(свойство обратных ребер) Пусть G связный граф,
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
Лемма 1.2
(свойство обратных ребер) Пусть G связный граф, T дерево поиска в глубину,
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Свойство обратных ребер
Лемма 1.2
(свойство обратных ребер) Пусть G связный граф, T дерево поиска в глубину, а uv обратное ребро,
Расин О.В. |
Поиск в графе |
|
|