Перейти к содержимому


lfif

Регистрация: 25 Jan 2020
Offline Активность: 15 May 2020 15:38
*****

Мои сообщения

В теме: Поиск в глубину

03 February 2020 - 18:46

Поиск в глубину (англ. depth-first search, DFS) – это рекурсивный алгоритм обхода вершин графа. Если метод поиска в ширину производился симметрично (вершины графа просматривались по уровням), то данный метод предполагает продвижение вглубь до тех пор, пока это возможно. Невозможность дальнейшего продвижения, означает, что следующим шагом будет переход на последнюю, имеющую несколько вариантов движения (один из которых исследован полностью), ранее посещенная вершина.

Пошаговое представление

1. Выбираем любую вершину из еще не пройденных, обозначим ее как v

2. Запускаем процедуру dfs(v)

  • Помечаем вершину v как пройденную
  • Для каждой не пройденной смежной с v вершиной (назовем ее to) запускаем dfs(to)

3. Повторяем шаги 1 и 2, пока все вершины не окажутся пройденными

Алгоритм работает за O (N+M)

Применение алгоритма

  • Поиск любого пути в графе
  • Есть ли путь из вершины S в вершину F
  • Связный ли граф
  • Сколько компонент связности
  • Поиск лексикографически первого пути в графе
  • Топологическая сортировка:
    Запускаем серию поисков в глубину, чтобы обойти все вершины графа. Отсортируем вершины по времени выхода по убыванию - это и будет ответом.
  • Задача LCA (наименьший общий предок)
Реализация
Рассмотрим задачу:
В стране Z есть N городов, которые соединены M дорогами. По дорогам можно ездить в обоих направлениях. Между двумя городами могут существовать несколько дорог, также дорога может вести из города в его же самого. Правительство страны хочет определить количество изолированных друг от друга областей в стране. Область – это набор городов, где между любой парой городов есть путь. Помогите правительству определить это количество.
Формат ввода:
N, M – количество городов и дорог.
Далее следует M строк с описанием дорог. Каждая дорога описывается парой чисел – города которые она соединяет.
Решение:
Решение задачи сводится к нахождению количества компонент связности в графе.
int32_t main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
    	int x, y;
    	cin >> x >> y; x--; y--;
    	if (x == y) continue;
    	g[x].insert(y);
    	g[y].insert(x);
	}
	int k = 0;
	for (int i = 0; i < n; ++i) p[i] = 0;
	for (int i = 0; i < n; ++i) {
    	if (!p[i]){
        	dfs(i);
        	k++;
    	}
	}
	cout << k << endl;
	return 0;
}
  • Прочитаем список смежности графа
  • Пометим все вершины как не пройденные
  • Пройдем по всем вершинам

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

  • Запустим dfs от этой вершины
  • Увеличим ответ
  • Выведем ответ
Сам dfs:
set < int > g[N];
bool p[N];
void dfs (int v){
	if (!p[v]){
    	p[v] = 1;
    	for (auto to:g[v]){
        	if (!p[to]) dfs(to);
    	}
	}
}


Сдать задачу:http://dl.gsu.by/tas...=1062969&cid=19
Если ссылка не открывается:
dl.gsu.by Олимпиады по информатике Гомельская гор. 13.10.2012 изолированные города