Поиск в графе 2
.pdf
Задача поиска в графе |
Поиск в глубину |
|
|
Поиск в графе
Расин О.В.
14 апреля 2015 г.
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Задача поиска в графе
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Некоторые договоренности
Для упрощения обозначений будем предполагать, что
граф G = (V G; EG) связный
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Некоторые договоренности
Для упрощения обозначений будем предполагать, что
граф G = (V G; EG) связный
через n обозначается число вершин в графе, а через m число ребер
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Некоторые договоренности
Для упрощения обозначений будем предполагать, что
граф G = (V G; EG) связный
через n обозначается число вершин в графе, а через m число ребер
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Основные струкутры данных и глобальные переменные
В алгоритме поиска в глубину используются следующие структуры данных
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Основные струкутры данных и глобальные переменные
В алгоритме поиска в глубину используются следующие структуры данных
логический массив Visit длины n (Visit[u] = true, если вершина u посещалась; в противном случае Visit[u] = f alse)
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Основные струкутры данных и глобальные переменные
В алгоритме поиска в глубину используются следующие структуры данных
логический массив Visit длины n (Visit[u] = true, если вершина u посещалась; в противном случае Visit[u] = f alse)
массив Visit длины n (Father[u] = v, если из вершины v, впервые обнаружена вершина u)
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Основные струкутры данных и глобальные переменные
В алгоритме поиска в глубину используются следующие структуры данных
логический массив Visit длины n (Visit[u] = true, если вершина u посещалась; в противном случае Visit[u] = f alse)
массив Visit длины n (Father[u] = v, если из вершины v, впервые обнаружена вершина u)
если u начальная вершина поиска, то Father[u] = 0;
Расин О.В. |
Поиск в графе |
|
|
Задача поиска в графе |
Поиск в глубину |
|
|
Основные струкутры данных и глобальные переменные
В алгоритме поиска в глубину используются следующие структуры данных
логический массив Visit длины n (Visit[u] = true, если вершина u посещалась; в противном случае Visit[u] = f alse)
массив Visit длины n (Father[u] = v, если из вершины v, впервые обнаружена вершина u)
если u начальная вершина поиска, то Father[u] = 0;
массив num длины n (хранит порядок, в котором посещались вершины )
Расин О.В. |
Поиск в графе |
|
|