Поиск в графе 2
.pdf
Задача поиска в графе |
Поиск в глубину |
|
|
Основные струкутры данных и глобальные переменные
В алгоритме поиска в глубину используются следующие структуры данных
логический массив Visit длины n (Visit[u] = true, если вершина u посещалась; в противном случае Visit[u] = f alse)
массив Visit длины n (Father[u] = v, если из вершины v, впервые обнаружена вершина u)
если u начальная вершина поиска, то Father[u] = 0;
массив num длины n (хранит порядок, в котором
посещались вершины )
если u начальная вершина поиска, то num[u] = 1;
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Основные струкутры данных и глобальные переменные
В алгоритме поиска в глубину используются следующие структуры данных
логический массив Visit длины n (Visit[u] = true, если вершина u посещалась; в противном случае Visit[u] = f alse)
массив Visit длины n (Father[u] = v, если из вершины v, впервые обнаружена вершина u)
если u начальная вершина поиска, то Father[u] = 0;
массив num длины n (хранит порядок, в котором
посещались вершины )
если u начальная вершина поиска, то num[u] = 1;
целочисленная глобальная переменная counterNum для присваивания порядковых номеров
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Поиск в глубину
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Поиск в глубину
Стратегия поиска в глубину состоит в том, что когда мы приходим в вершину v,
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Поиск в глубину
Стратегия поиска в глубину состоит в том, что когда мы приходим в вершину v, то если у v есть непросмотренный сосед
u, то мы продолжаем поиск из u,
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Поиск в глубину
Стратегия поиска в глубину состоит в том, что когда мы приходим в вершину v, то если у v есть непросмотренный сосед
u, то мы продолжаем поиск из u,
если все соседи v просмотрены, то возвращаемся в вершину v0, из который мы пришли в v.
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Поиск в глубину
Стратегия поиска в глубину состоит в том, что когда мы приходим в вершину v, то если у v есть непросмотренный сосед
u, то мы продолжаем поиск из u,
если все соседи v просмотрены, то возвращаемся в вершину v0, из который мы пришли в v.
Для реализации этой стратегии используется стек Stack
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Поиск в глубину
Стратегия поиска в глубину состоит в том, что когда мы приходим в вершину v, то если у v есть непросмотренный сосед
u, то мы продолжаем поиск из u,
если все соседи v просмотрены, то возвращаемся в вершину v0, из который мы пришли в v.
Для реализации этой стратегии используется стек Stack
Алгоритм можно представить в виде следующей последовательности действий
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Операции для работы со стеком и списком
Для более компактной записи алгоритма введем обозначения некоторых операций
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Операции для работы со стеком и списком
Для более компактной записи алгоритма введем обозначения некоторых операций
метод Push (для вставки вершины в стек)
Расин О.В. |
Поиск в графе |
|
|