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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

берем такую вершину v, добавляем на вершину стека (Stack:Push(v)); Visit[v] := 1, num[v] := 1, counterNum + +

Перейти к шагу 2

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

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

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

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

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

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

берем такую вершину v, добавляем на вершину стека (Stack:Push(v)); Visit[v] := 1, num[v] := 1, counterNum + +

Перейти к шагу 2 Если все вершины просмотрены,

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

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

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

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

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

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

берем такую вершину v, добавляем на вершину стека (Stack:Push(v)); Visit[v] := 1, num[v] := 1, counterNum + +

Перейти к шагу 2 Если все вершины просмотрены, то перейти к шагу 4.

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

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

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

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

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

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

берем такую вершину v, добавляем на вершину стека (Stack:Push(v)); Visit[v] := 1, num[v] := 1, counterNum + +

Перейти к шагу 2 Если все вершины просмотрены, то перейти к шагу 4.

2. Если Stack 6= 0/, то просматриваем очередную вершину из стека v := Stack:Top() перейти к шагу 3.

Åñëè Stack = 0/,

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

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

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

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

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

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

берем такую вершину v, добавляем на вершину стека (Stack:Push(v)); Visit[v] := 1, num[v] := 1, counterNum + +

Перейти к шагу 2 Если все вершины просмотрены, то перейти к шагу 4.

2. Если Stack 6= 0/, то просматриваем очередную вершину из стека v := Stack:Top() перейти к шагу 3.

Если Stack = 0/, то перейти к шагу 4.

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

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

Формулировка алгоритма

3. Если список смежности v просмотрен до конца, то Stack:Pop() (удаляем v из стека)

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

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

Формулировка алгоритма

3. Если список смежности v просмотрен до конца, то Stack:Pop() (удаляем v из стека)

Иначе получаем очередной элемент списка смежности (u := copyList[v]:GetNext()).

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

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

Формулировка алгоритма

3. Если список смежности v просмотрен до конца, то Stack:Pop() (удаляем v из стека)

Иначе получаем очередной элемент списка смежности (u := copyList[v]:GetNext()).

а) Если u еще не посещалась (Visit[u] = 0), то

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