Алгоритм обхода графа в глубину
олимпиадные задания по информатике и икт (9 класс)

Теория графов. Алгоритм обхода графа в глубину

Шафоростова Елена Петровна

педагог дополнительного образования

Детский технопарк «Кванториум», г. Липецк

Поиск в глубину (Depth – first search, DFS) – это один из основных алгоритмов на графах. В результате поиска в глубину находится первый путь в графе.

Некоторые применения алгоритма:

• Поиск любого пути в графе.
• Поиск лексикографически первого пути в графе.
• Проверка, является ли одна вершина дерева предком другой.

Стратегия поиска в глубину, как следует из её названия, состоит в том, чтобы идти "вглубь" графа, насколько это возможно. При выполнении поиска в глубину исследуются все ребра, выходящие из вершины, открытой последней, и покидает вершину, только когда не остается неисследованных ребер − при этом происходит возврат в вершину, из которой была открыта вершина v. Этот процесс продолжается до тех пор, пока не будут открыты все вершины, достижимые из исходной. Если при этом остаются неоткрытые вершины, то одна из них выбирается в качестве новой исходной вершины и поиск повторяется уже из нее. Этот процесс повторяется до тех пор, пока не будут открыты все вершины.

Пусть дан некоторый граф, и мы хотим по ребрам обойти все его вершины.

Задачи из реальной жизни:

1) Вы попали в лабиринт, и вам нужно найти сокровища, а для этого нужно пройти по всем проходам и осмотреть все пещеры.

2) У вас есть файловая система, вы находитесь в каком-то ее месте и хотите найти какой-то файл.

Рассмотрим граф. 1 – начальная вершина, пойдем из нее в первую попавшуюся вершину, например, в 2. Из 2 идем в 3, далее в 4. Из 4 наверх идти нет смысла, там мы уже были, следовательно, пойдем в 5. Попали в вершину, у которой все соседи помечены, мы в них уже были. Возвращаемся назад и ищем непомеченных соседей.

Доходим до вершины 2 и видим, что не помечена вершина 6, идем в нее, затем в 7, назад и в 8. И в конце из 1 идем в 9. Поднимаемся наверх в 1 и видим, что все соседи помечены, таким образом обошли весь граф.

Алгоритм:

Помимо матрицы смежности, которая описывает граф, нам потребуется логический массив used, в котором будем хранить признак того, была ли посещена вершина, изначально все вершины не посещены (false). Запускаем функцию из стартовой вершины v. Проходим по строке матрицы смежности для вершины v и ищем, с какими еще вершинами есть ребро. Если нашлось ребро (в матрице смежности значение 1), то помечаем соответствующую вершину в массиве used и запускаем функцию уже для новой вершины. И т.д. до тех пор, пока в массиве used все вершины не примут значение true.

vector > graph;

vector used;

int n;

void dfs (int v)

{

if (used[v])

{

return;

}

used[v]=true;

for(int i=0; i

{

if (graph[v][i]==1 && !used[i])

{

dfs(i);

}

}

}

int main() {

int k, x;

cin>>n>>k;

(n, false);

for(int i=0; i

{

(vector ());

for (int j=0; j

{

cin>>x;

graph[i].push_back(x);

}

}

dfs(k-1);

return 0;

}

Пример: Задача №150 из темы Теория графов – 1 (сайт )

В клубе N человек. Многие из них - друзья. Так же известно, что друзья друзей так же являются друзьями. Требуется выяснить, сколько всего друзей у конкретного человека в клубе.

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

В первой строке входного файла заданы два числа: N и S (1 ≤ N ≤ 100; 1 ≤ S ≤ N), где N - количество человек в клубе, а S – номер конкретного человека. В следующих N строках записано по N чисел - матрица смежности, состоящая из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что люди с номерами i и j – друзья, а 0 – выражает неопределенность.

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

В выходной файл выведите количество гарантированных друзей у человека с номером S, помня о транзитивности дружбы.

Пример

#include

#include

using namespace std;

vector > graph;

vector used;

int n, ans = 0;

void dfs(int v) {

if (used[v]) {

return;

}

used[v] = true;

for (int i = 0; i < n; i ++) {

if (graph[v][i] && !used[i]) {

dfs(i);

}

}

}

int main() {

int k, x,i,j;

cin>>n>>k;

(n, false);

for (i = 0; i < n; i ++) {

(vector());

for (j = 0; j < n; j ++) {

cin>>x;

graph[i].push_back(x);

}

}

for (i=0; i

for(j=0; j

if(graph[i][j])

graph[j][i]=1;

dfs(k - 1);

for(i=0; i

if (used[i])

ans++;

cout<

return 0;

}

Литература и интернет-ресурсы

1. А. Шень. Программирование: теоремы и задачи. – М.: МЦНМО, 2004. Второе издание, исправленное и дополненное.
2. Курс сайта «Введение в теоретическую информатику». Александр Шень.
3. Курс «Олимпиадные задачи по программированию». М.С. Густокашин. Электронный ресурс.
4. Ворожцов А.В., Винокуров Н.А. Лекции «Алгоритмы: построение, анализ и реализация на языке программирования Си». – М.: Издательство МФТИ, 2007.
5. Школа программиста. Электронный ресурс.