16
правок
Изменения
Новая страница: «'''Обход в глубину''' (поиск в глубину, англ. Depth-First Search, DFS) - один из основных методов обхода г…»
'''Обход в глубину''' (поиск в глубину, англ. Depth-First Search, DFS) - один из основных методов обхода графа, часто используемый для [[Использование обхода в глубину для проверки связности|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки|топологической сортировки]].
== Алгоритм ==
=== Общая идея ===
Общая идея алгоритма состоит в следующем: для каждой ''не пройденной'' вершины необходимо найти все ''не пройденные'' смежные вершины и повторить поиск для них.
=== Пошаговое представление ===
#Выбираем любую вершину из еще ''не пройденных'', обозначим ее как u.
#Запускаем процедуру DFS(u)
#*Помечаем вершину u как ''пройденную''
#*Для каждой ''не пройденной'' смежной с u вершиной (назовем ее v) запускаем DFS(v)
#Повторяем шаги 1 и 2, пока все вершины не окажутся ''пройденными''.
=== Реализация ===
vector<bool> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах
void dfs(int u)
{
visited[u] = true; //помечаем вершину как пройденную
for (v таких, что (u, v) - ребро в G) //проходим по смежным с u вершинам
if (!visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
dfs(v);
}
int main()
{
... //задание графа G с количеством вершин n.
visited.assign(n, false); //в начале все вершины в графе ''не пройденные''
for (int i = 0; i < n; ++i) //проходим по всем вершинам графа...
if (!visited[i]) //...не забыв проверить, были мы уже в очередной вершине или нет
dfs(i);
return 0;
}
== Цвета вершин ==
Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей.<br />
Поэтому в процессе алгоритма вершинам задают некоторые цвета:<br />
:если вершина ''белая'', значит, мы в ней еще не были, вершина ''не пройдена'';<br />
:''серая'' - вершина ''проходится'' в текущей процедуре DFS;<br />
:''черная'' - вершина ''пройдена'', все итерации DFS от нее завершены.<br />
Такие "метки" в основном используются при [[Использование обхода в глубину для поиска цикла в ориентированном графе|поиске цикла]].
=== Реализация ===
Отличие реализации с цветами от предыдущей лишь в массиве visited, который мы назовем теперь color, и дополнительной ''черной'' "метки". При этом цвета вершин будут заданы следующим образом: ''белый'' - 0, ''серый'' - 1, ''черный'' - 2. Все отличия помечены '''жирным''' шрифтом.
vector<'''int'''> '''color'''; //вектор для хранения информации '''о цвете''' вершин
void dfs(int u)
{
'''color[u] = 1; //раскрашиваем вершину в ''серый'' цвет'''
for (v таких, что (u, v) - ребро в G) //проходим по смежным с u вершинам
if (!color[v]) //проверяем, не находились ли мы ранее в выбранной вершине, '''условие не требует изменений,'''
dfs(v); '''//поскольку мы считаем вершину "не пройденной" только тогда, когда она ''белого'' цвета, т.е. когда color[v] = 0'''
'''color[u] = 2; //раскрашиваем вершину в ''черный'' цвет'''
}
int main()
{
... //задание графа G с количеством вершин n.
'''color.assign(n, 0);''' //в начале все вершины в графе ''не пройденные'', '''т.е. ''белые''.'''
for (int i = 0; i < n; ++i) //проходим по всем вершинам графа...
if (!visited[i]) //...не забыв проверить, были мы уже в очередной вершине или нет
dfs(i);
return 0;
}
== Алгоритм ==
=== Общая идея ===
Общая идея алгоритма состоит в следующем: для каждой ''не пройденной'' вершины необходимо найти все ''не пройденные'' смежные вершины и повторить поиск для них.
=== Пошаговое представление ===
#Выбираем любую вершину из еще ''не пройденных'', обозначим ее как u.
#Запускаем процедуру DFS(u)
#*Помечаем вершину u как ''пройденную''
#*Для каждой ''не пройденной'' смежной с u вершиной (назовем ее v) запускаем DFS(v)
#Повторяем шаги 1 и 2, пока все вершины не окажутся ''пройденными''.
=== Реализация ===
vector<bool> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах
void dfs(int u)
{
visited[u] = true; //помечаем вершину как пройденную
for (v таких, что (u, v) - ребро в G) //проходим по смежным с u вершинам
if (!visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
dfs(v);
}
int main()
{
... //задание графа G с количеством вершин n.
visited.assign(n, false); //в начале все вершины в графе ''не пройденные''
for (int i = 0; i < n; ++i) //проходим по всем вершинам графа...
if (!visited[i]) //...не забыв проверить, были мы уже в очередной вершине или нет
dfs(i);
return 0;
}
== Цвета вершин ==
Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей.<br />
Поэтому в процессе алгоритма вершинам задают некоторые цвета:<br />
:если вершина ''белая'', значит, мы в ней еще не были, вершина ''не пройдена'';<br />
:''серая'' - вершина ''проходится'' в текущей процедуре DFS;<br />
:''черная'' - вершина ''пройдена'', все итерации DFS от нее завершены.<br />
Такие "метки" в основном используются при [[Использование обхода в глубину для поиска цикла в ориентированном графе|поиске цикла]].
=== Реализация ===
Отличие реализации с цветами от предыдущей лишь в массиве visited, который мы назовем теперь color, и дополнительной ''черной'' "метки". При этом цвета вершин будут заданы следующим образом: ''белый'' - 0, ''серый'' - 1, ''черный'' - 2. Все отличия помечены '''жирным''' шрифтом.
vector<'''int'''> '''color'''; //вектор для хранения информации '''о цвете''' вершин
void dfs(int u)
{
'''color[u] = 1; //раскрашиваем вершину в ''серый'' цвет'''
for (v таких, что (u, v) - ребро в G) //проходим по смежным с u вершинам
if (!color[v]) //проверяем, не находились ли мы ранее в выбранной вершине, '''условие не требует изменений,'''
dfs(v); '''//поскольку мы считаем вершину "не пройденной" только тогда, когда она ''белого'' цвета, т.е. когда color[v] = 0'''
'''color[u] = 2; //раскрашиваем вершину в ''черный'' цвет'''
}
int main()
{
... //задание графа G с количеством вершин n.
'''color.assign(n, 0);''' //в начале все вершины в графе ''не пройденные'', '''т.е. ''белые''.'''
for (int i = 0; i < n; ++i) //проходим по всем вершинам графа...
if (!visited[i]) //...не забыв проверить, были мы уже в очередной вершине или нет
dfs(i);
return 0;
}
