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

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

Операции для работы со стеком и списком

Для более компактной записи алгоритма введем обозначения некоторых операций

метод Push (для вставки вершины в стек)

метод Pop (читает вершину на вершине стека и удаляет ее из стека)

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

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

Операции для работы со стеком и списком

Для более компактной записи алгоритма введем обозначения некоторых операций

метод Push (для вставки вершины в стек)

метод Pop (читает вершину на вершине стека и удаляет ее из стека)

метод Top (читает вершину стека без ее удаления из стека)

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

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

Операции для работы со стеком и списком

Для более компактной записи алгоритма введем обозначения некоторых операций

метод Push (для вставки вершины в стек)

метод Pop (читает вершину на вершине стека и удаляет ее из стека)

метод Top (читает вершину стека без ее удаления из стека)

Для прохода по списку используется метод getNext, который читает следующий элемент списка,

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

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

Операции для работы со стеком и списком

Для более компактной записи алгоритма введем обозначения некоторых операций

метод Push (для вставки вершины в стек)

метод Pop (читает вершину на вершине стека и удаляет ее из стека)

метод Top (читает вершину стека без ее удаления из стека)

Для прохода по списку используется метод getNext, который читает следующий элемент списка, заметим, что если чтение списка еще не производилось, то читается первый элемент

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

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

Поиск в глубину (формулировка алгоритма)

0. (инициализация) Для каждой вершины v 2V присваиваем

Visit[v] := 0,

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

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

Поиск в глубину (формулировка алгоритма)

0. (инициализация) Для каждой вершины v 2V присваиваем

Visit[v] := 0, Father[v] := 0

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

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

Поиск в глубину (формулировка алгоритма)

0. (инициализация) Для каждой вершины v 2V присваиваем

Visit[v] := 0, Father[v] := 0num[v] := 0;

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

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

Поиск в глубину (формулировка алгоритма)

0. (инициализация) Для каждой вершины v 2V присваиваем

Visit[v] := 0, Father[v] := 0num[v] := 0; counterNum := 1

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

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

Поиск в глубину (формулировка алгоритма)

0.(инициализация) Для каждой вершины v 2V присваиваем

Visit[v] := 0, Father[v] := 0num[v] := 0; counterNum := 1

1.Если есть непросмотренные вершины, т. е. существует v 2V , что Visit[v] = 0,

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

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

Поиск в глубину (формулировка алгоритма)

0.(инициализация) Для каждой вершины v 2V присваиваем

Visit[v] := 0, Father[v] := 0num[v] := 0; counterNum := 1

1.Если есть непросмотренные вершины, т. е. существует v 2V , что Visit[v] = 0,

берем такую вершину v, добавляем на вершину стека (Stack:Push(v));

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