Обход графа в глубину

1. Обход графа в глубину

Рыбаченко И.А. 8К61
2017

2. Неориентированный граф

1 1 9
11
7
8
14
6
5
2
2
6
7
10
12
13
5
3
4
3
4
8

3. Ориентированный граф

1 1 9
11
7
8
14
6
5
2 2
6
7
10
12
13
5
3
4
3
4
8

4. Реализация

vector < vector<int> > g; // граф
int n; // число вершин
vector<char> used;
void dfs (int v) {
used[v] = true;
for (vector<int>::iterator i=g[v].begin(); i!=g[v].end(); ++i)
if (!used[*i])
dfs (*i);
}

5. Применение

• Поиск любого пути в графе.
• Поиск лексикографически первого пути в графе.
• Проверка, является ли одна вершина дерева предком другой:
• Проверка графа на ацикличность и нахождение цикла
• Поиск компонент сильной связности
• Поиск мостов
• И многое другое