Название работы	Кол-во страниц	Размер
Информационный поиск	1	126.38kb.
Практическое задание №1. Классификация информационно-поискового пространства...	1	110.7kb.
Задача оптимизации туристических групп Поиск решения и сценарии.	1	171.42kb.
В. П. Захаров Информационные системы (документальный поиск)	1	41.64kb.
Специальные призы Специальным призом «За творческий поиск»	1	54.55kb.
Информационный поиск в семантическом проектном репозитории	1	98.37kb.
1. Воспитывать культуру общения на английском языке	1	19.25kb.
1. поиск алмазов	1	31.61kb.
Элективный курс «Экология Белгородской области»	1	172kb.
Концепция энергоресурсосберегающей деятельности в промышленности Н.	1	110.26kb.
Л. Н. Андреев «Рассказ о семи повешенных»	7	996.85kb.
Методические указания по выполению домашнего задания по дисциплине...	1	287.71kb.
Викторина для любознательных: «Занимательная биология»	1	9.92kb.

Поиск в глубину

Задан граф G с N вершинами и M дугами. Поиск в глубину применяется во многих задачах, например в задачах поиска компонент связности, мостов, точек сочленения, сильно связных компонент, топологической сортировке. Поиск в глубину реализуется следующей рекурсивной процедурой:

DFS(a)

Пометить вершину a как пройденную

Для любого ребра (a,b)

Если вершина b не пройдена, то

DFS(b)
Здесь a — некоторая вершина графа.
Поиск компонент связности

Пусть G — неорграф. Разобъем множество его вершин на компоненты связности по следующему принципу: две вершины лежат в одной компоненте связности, когда есть путь из одной вершины в другую.

Если выполнить DFS(a) при условии, что все вершины изначально не помечены, то алгоритм посетит все вершины, достижимые из a. Поэтому его можно применять для поиска связных компонент. Для этого будем для каждой помеченной вершины хранить номер ее компоненты связности, который будем также называть цветом. Непройденные вершины считаем непокрашенными. Алгоритм работает так:
DFS(a,c)

Покрасить вершину a в цвет c

Для любого ребра (a,b)

Если вершина b не покрашена, то

DFS(b,c)
CONNECTED_COMPONENTS

Изначально все вершины не покрашены

c := 0

Для любой вершины a,

Если a не покрашена, то

c := c+1

DFS(a,c)
Топологическая сортировка
Пусть задан ориентированный граф G без циклов. Топологической сортировкой в нем называется такое упорядочение его вершин, что для любого ребра (a,b), вершина a расположена раньше вершины b в этом упорядочении. Ясно, что может существовать несколько топологических сортировок нашего графа.
Для того, чтобы найти топологическую сортировку графа, упорядочим вершины в порядке убывания времени выхода, т. е. момента, в который алгоритм поиска в глубину закончил обработку вершины. Это и будет топологической сортировкой.

DFS(a)

Пометить вершину a

Для любого ребра (a,b),

Если вершина b не помечена, то

DFS(b)

Добавить a в начало списка вершин
TOPOLOGICAL_SORT

Изначально список вершин пуст, никакая вершина не помечена

Для любой вершины a,

Если a не помечена, то

DFS(a)