Обход в глубину, цвета вершин — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники)
(Дерево обхода в глубину)
Строка 72: Строка 72:
 
== Дерево обхода в глубину ==
 
== Дерево обхода в глубину ==
 
[[Image:tree_edges.png|thumb|270px|Типы ребер, определяемые деревом обхода]]
 
[[Image:tree_edges.png|thumb|270px|Типы ребер, определяемые деревом обхода]]
Рассмотрим подграф предшествования обхода в глубину <tex>G_p = (V, E_p)</tex>, где <tex>E_p = \{(p[u], u) : u \in V,\ p[u] \neq NIL\}</tex>, где в свою очередь <tex>p[u]</tex> — вершина, от которой был вызван <tex>dfs(u)\ </tex> (для вершин, от которых <tex>dfs</tex> был вызван нерекурсивно это значение соответственно равно <tex>NIL</tex>). Подграф предшествования поиска в глубину образует ''лес обхода в глубину'', который состоит из нескольких ''деревьев обхода в глубину''. Назовем ''ребрами дерева'' те ребра из <tex>G</tex>, которые вошли в <tex>G_p</tex>. Рассмотрим такие ребра графа <tex>G</tex>, которые не попали в <tex>G_p</tex>. Ребра <tex>(u, v)</tex>, соединяющие вершину <tex>u</tex> с её предком <tex>v</tex> в дереве обхода в глубину назовем ''обратными ребрами''. Ребра <tex>(u, v)</tex>, не являющиеся ребрами дерева и соединяющие вершину <tex>u</tex> с её потомком <tex>v</tex> в дереве обхода в глубину назовем ''прямыми ребрами''. Все остальные ребра назовем ''перекрестными ребрами'' — такие ребра могут соединять вершины одного и того же дерева обхода в глубину, когда ни одна из вершин не является предком другой, или соединять вершины в разных деревьях.
+
Рассмотрим подграф предшествования обхода в глубину <tex>G_p = (V, E_p)</tex>, где <tex>E_p = \{(p[u], u) : u \in V,\ p[u] \neq NIL\}</tex>, где в свою очередь <tex>p[u]</tex> — вершина, от которой был вызван <tex>dfs(u)\ </tex> (для вершин, от которых <tex>dfs</tex> был вызван нерекурсивно это значение соответственно равно <tex>NIL</tex>). Подграф предшествования поиска в глубину образует ''лес обхода в глубину'', который состоит из нескольких ''деревьев обхода в глубину''. С помощью полученного леса можно классифицировать ребра графа <tex>G</tex>:
 +
* ''Ребрами дерева'' назовем те ребра из <tex>G</tex>, которые вошли в <tex>G_p</tex>.  
 +
* Ребра <tex>(u, v)</tex>, соединяющие вершину <tex>u</tex> с её предком <tex>v</tex> в дереве обхода в глубину назовем ''обратными ребрами'' (для неориентированного графа предок должен быть ''не родителем'', так как иначе ребро будет являться ребром дерева).  
 +
* Ребра <tex>(u, v)</tex>, не являющиеся ребрами дерева и соединяющие вершину <tex>u</tex> с её потомком <tex>v</tex> в дереве обхода в глубину назовем ''прямыми ребрами'' (в неориентированном графе нет разницы между прямыми и обратными ребрами, поэтому все такие ребра считаются обратными).  
 +
* Все остальные ребра назовем ''перекрестными ребрами'' — такие ребра могут соединять вершины одного и того же дерева обхода в глубину, когда ни одна из вершин не является предком другой, или соединять вершины в разных деревьях.
 
Алгоритм <tex>dfs</tex> можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро <tex>(u, v)</tex> можно классифицировать при помощи цвета вершины <tex>v</tex> при первом его исследовании, а именно:
 
Алгоритм <tex>dfs</tex> можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро <tex>(u, v)</tex> можно классифицировать при помощи цвета вершины <tex>v</tex> при первом его исследовании, а именно:
 
* Белый цвет вершины <tex>v</tex> по определению <tex>dfs</tex> говорит о том, что это ''ребро дерева''.
 
* Белый цвет вершины <tex>v</tex> по определению <tex>dfs</tex> говорит о том, что это ''ребро дерева''.
* Серый цвет в силу того, что серые вершины всегда образуют нисходящий путь в каком-либо из деревьев <tex>dfs</tex> и встреченная вершина <tex>v</tex> лежит на нем выше вершины <tex>u</tex>, определяет ''обратное ребро''.
+
* Серый цвет в силу того, что серые вершины всегда образуют нисходящий путь в каком-либо из деревьев <tex>dfs</tex> и встреченная вершина <tex>v</tex> лежит на нем выше вершины <tex>u</tex>, определяет ''обратное ребро''. (для неориентированного графа необходимо проверить условие <tex>v \neq p[u]</tex>)
 
* Черный цвет, соответственно, указывает на ''прямое'' или ''перекрестное ребро''.
 
* Черный цвет, соответственно, указывает на ''прямое'' или ''перекрестное ребро''.
  

Версия 07:49, 25 октября 2011

Обход в глубину (поиск в глубину, англ. Depth-First Search, DFS) - один из основных методов обхода графа, часто используемый для проверки связности, поиска цикла и компонент сильной связности и для топологической сортировки.

Алгоритм

Общая идея

Общая идея алгоритма состоит в следующем: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.

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

  1. Выбираем любую вершину из еще не пройденных, обозначим ее как [math]u[/math].
  2. Запускаем процедуру [math]dfs(u)[/math]
    • Помечаем вершину u как пройденную
    • Для каждой не пройденной смежной с [math]u[/math] вершиной (назовем ее [math]v[/math]) запускаем [math]dfs(v)[/math]
  3. Повторяем шаги 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;
}

Время работы

Оценим время работы обхода в глубину. Процедура [math]dfs[/math] вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие ребра [math]\{e\ |\ begin(e) = u\}[/math]. Всего таких ребер для всех вершин в графе [math]O(E)[/math], следовательно, время работы алгоритма оценивается как [math]O(V+E)[/math].

Цвета вершин

Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей.
Поэтому в процессе алгоритма вершинам задают некоторые цвета:

если вершина белая, значит, мы в ней еще не были, вершина не пройдена;
серая - вершина проходится в текущей процедуре [math]dfs[/math];
черная - вершина пройдена, все итерации [math]dfs[/math] от нее завершены.

Такие "метки" в основном используются при поиске цикла.

Реализация

Отличие реализации с цветами от предыдущей лишь в массиве 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 (!color[i])                    //...не забыв проверить, были мы уже в очередной вершине или нет
            dfs(i);
    return 0;
}

Дерево обхода в глубину

Типы ребер, определяемые деревом обхода

Рассмотрим подграф предшествования обхода в глубину [math]G_p = (V, E_p)[/math], где [math]E_p = \{(p[u], u) : u \in V,\ p[u] \neq NIL\}[/math], где в свою очередь [math]p[u][/math] — вершина, от которой был вызван [math]dfs(u)\ [/math] (для вершин, от которых [math]dfs[/math] был вызван нерекурсивно это значение соответственно равно [math]NIL[/math]). Подграф предшествования поиска в глубину образует лес обхода в глубину, который состоит из нескольких деревьев обхода в глубину. С помощью полученного леса можно классифицировать ребра графа [math]G[/math]:

  • Ребрами дерева назовем те ребра из [math]G[/math], которые вошли в [math]G_p[/math].
  • Ребра [math](u, v)[/math], соединяющие вершину [math]u[/math] с её предком [math]v[/math] в дереве обхода в глубину назовем обратными ребрами (для неориентированного графа предок должен быть не родителем, так как иначе ребро будет являться ребром дерева).
  • Ребра [math](u, v)[/math], не являющиеся ребрами дерева и соединяющие вершину [math]u[/math] с её потомком [math]v[/math] в дереве обхода в глубину назовем прямыми ребрами (в неориентированном графе нет разницы между прямыми и обратными ребрами, поэтому все такие ребра считаются обратными).
  • Все остальные ребра назовем перекрестными ребрами — такие ребра могут соединять вершины одного и того же дерева обхода в глубину, когда ни одна из вершин не является предком другой, или соединять вершины в разных деревьях.

Алгоритм [math]dfs[/math] можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро [math](u, v)[/math] можно классифицировать при помощи цвета вершины [math]v[/math] при первом его исследовании, а именно:

  • Белый цвет вершины [math]v[/math] по определению [math]dfs[/math] говорит о том, что это ребро дерева.
  • Серый цвет в силу того, что серые вершины всегда образуют нисходящий путь в каком-либо из деревьев [math]dfs[/math] и встреченная вершина [math]v[/math] лежит на нем выше вершины [math]u[/math], определяет обратное ребро. (для неориентированного графа необходимо проверить условие [math]v \neq p[u][/math])
  • Черный цвет, соответственно, указывает на прямое или перекрестное ребро.

Источники