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

Нравится

Не нравится

Санек 21 дек 2011

Поиск в глубину, применяется для

*решения произвольных задач на графах, требующих соответствующего порядка обхода ("в глубину") графа; раскрашивая пройденные вершины и/или дуги можно управлять порядком и способами обхода (например, однократное или многократное использование дуг и вершин)

*построения множества истоков и стоков (как истоков на транспонированном графе)

*построения сильносвязных компонент (ССК) графа ССК - это множество вершин, каждая из которых достижима из всех вершин ССК

Пример задачи на поиск в глубину.

Грядки

Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:
из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.

Входные данные

В первой строке входного файла INPUT.TXT находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. (1 <= N, M <= 200)

Выходные данные

В выходной файл OUTPUT.TXT выведите количество грядок на садовом участке.

Примеры

INPUT.TXT

5 10

##......#.

.#..#...#.

.###....#.

..##....#.

........#.

OUTPUT.TXT

3

Основной код

var g:array [1..200,1..200] of char; k,i,j,n,m:integer;
procedure dfs(x,y:longint);
begin
g[x,y]:='o';
if (y<m )and(g[x,y+1]='#') then dfs(x,y+1);
if (y>1 )and(g[x,y-1]='#') then dfs(x,y-1);
if (x<n )and(g[x+1,y]='#') then dfs(x+1,y);
if (x>1 )and(g[x-1,y]='#') then dfs(x-1,y);
end;
begin
readln(n,m);
k:=0;
for i:=1 to n do begin
   				for j:=1 to m do
   				read(g[i,j]);
  readln;
end;
for i:=1 to n do
  for j:=1 to m do begin
                	if (g[i,j]='#')
 					then begin
       					k:=k+1;
       					dfs(i,j);
                      	end;
                	end;
writeln(k);
end.

Ответить

Нравится

Не нравится

petuhovskiy 06 янв 2012

Стандартный поиск в глубину

procedure DFS (v : longint);
var i : longint;
begin
	p[v]:=true;
	for i:=1 to n do if (a[v,i]=1)and(not(p[i])) then DFS(i);
end;

И ещё поиск в гллубину который находит кратчайший путь

procedure DFS (v,d : longint);
var i : longint;
begin
	p[v]:=d;;
	for i:=1 to n do if (a[v,i]=1)and((p[i]=-1)or(d+1<p[i])) then DFS(i,d+1);
end;

В этом алгоритме надо :
1. Забить массив p -1
2. Пускать глубину DFS(s,0);

Ответить

Нравится

Не нравится

LVP 08 янв 2012

Молодец, Артурчик!!!

Ответить

Нравится

Не нравится

lfif 03 фев 2020

Поиск в глубину (англ. 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 изолированные города

Ответить

олимпиадники-информатики