Использование обхода в глубину для поиска точек сочленения — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Задача == Дан связный [[Основные определения…»)
 
Строка 14: Строка 14:
  
 
== Реализация ==
 
== Реализация ==
bool used[];
+
В массиве <tex>answer[]</tex> для каждой вершины содержится булево значение - является она точкой сочленения или нет. Изначально все значения '''false'''.
int tin[];
+
 
int up[];
+
  '''dfs'''<tex>(u, \, prev)</tex>
bool answer[];                              //для каждой вершины содержится булево значение - является она точкой сочленения или нет. изначально все значения false
+
     <tex>used[u] \leftarrow</tex>'''true'''
int time;
+
     <tex>tin[u] \leftarrow time</tex>                          //задание времени входа в вершину u
+
    <tex>up[u] \leftarrow time</tex>                          //задание начального значения up для вершины u
  void dfs(int u, int prev)
+
     <tex>time \leftarrow time + 1</tex>
{
+
    <tex>count \leftarrow 0</tex>                              //счетчик количества детей вершины u в дереве обхода
     used[u] = true;
+
     '''for '''<tex>(v : uv \in E)</tex>
     tin[u] = up[u] = time++;                //задание времени входа tin и начального значения up для вершины u
+
         '''if '''<tex>v = prev</tex>
     int count = 0;                          //счетчик количества детей вершины u в дереве обхода
+
             '''continue'''
     for (v : uv из E)
+
         '''if '''<tex>used[v]</tex>                            //v - предок вершины u, uv - обратное ребро
    {
+
             <tex>up[u] \leftarrow min(up[u], \, tin[v])</tex>
         if (v == prev)
+
         '''else'''                                  //v - ребенок вершины u
             continue;
+
             <tex>count \leftarrow count + 1</tex>
         if (used[v])                        //v - предок вершины u, uv - обратное ребро
+
             '''dfs'''<tex>(v, u)</tex>
             up[u] = min(up[u], tin[v]);
+
             <tex>up[u] \leftarrow min(up[u], \, up[v])</tex>
         else                               //v - ребенок вершины u
+
             '''if '''<tex>up[v] \ge tin[u]</tex>
        {
+
                 <tex>answer[u] \leftarrow</tex>'''true'''           //не существует обратного ребра из вершины v или ее потомка в предка вершины u. вершина u - точка сочленения
             ++count;
+
     '''if '''<tex>p = -1</tex>                              //является ли u корнем дерева обхода
             dfs(v, u);
+
         <tex>answer[u] \leftarrow (count > 1)</tex>;       //проверка количества детей у корня дерева
             up[u] = min(up[u], up[v]);
+
 
             if (up[v] >= tin[u])
 
                 answer[u] = true;           //не существует обратного ребра из вершины v или ее потомка в предка вершины u. вершина u - точка сочленения
 
        }
 
    }
 
     if (p == -1)                            //является ли u корнем дерева обхода
 
         answer[u] = (count > 1);           //проверка количества детей у корня дерева
 
}
 
 
int main()
 
{
 
    ...                                    //инициализация графа, выбор корня дерева обхода root
 
    time = 0;
 
    dfs(root, -1);
 
    return 0;
 
}
 
Для поиска точек сочленения в несвязном графе, необходимо модифицировать функцию main следующим образом:
 
int main()
 
{
 
    ...
 
    for (root из V)
 
        if (!used[root])
 
        {
 
            time = 0;
 
            dfs(root, -1);
 
        }
 
    return 0;
 
}
 
 
== Источники ==
 
== Источники ==
 
[http://e-maxx.ru/algo/ MAXimal::algo]
 
[http://e-maxx.ru/algo/ MAXimal::algo]

Версия 06:42, 1 декабря 2010

Задача

Дан связный неориентированный граф. Требуется найти все точки сочленения в нем.

Алгоритм

Запустим обход в глубину из произвольной вершины [math]root[/math] графа [math]G(V, E)[/math]. Рассмотрим [math]u \in V[/math]:

  1. [math]u \ne root[/math]. Тогда, если найдётся такой потомок [math]v[/math] вершины [math]u[/math] в дереве поиска, что ни из него, ни из какого-либо его потомка нет ребра в предка вершины [math]u[/math], то вершина [math]u[/math] будет являться точкой сочленения. В противном случае, вершина [math]u[/math] не является точкой сочленения.
  2. [math]u = root[/math]. [math]u[/math] - точка сочленения [math]\Leftrightarrow u[/math] имеет хотя бы двух сыновей в дереве поиска в глубину.

Пусть [math]tin[u][/math] - время входа поиска в глубину в вершину [math]u[/math]. Через [math]up[u][/math] обозначим минимум из времени захода в саму вершину [math]tin[u][/math], времен захода в каждую из вершин [math]p[/math], являющуюся концом некоторого обратного ребра [math](u,p)[/math], а также из всех значений [math]up[v][/math] для каждой вершины [math]v[/math], являющейся непосредственным сыном [math]u[/math] в дереве поиска.

Тогда, из вершины [math]u[/math] или её потомка есть обратное ребро в её предка [math]\Leftrightarrow \exists[/math] такой сын [math]v[/math], что [math]up[v] \lt tin[u][/math].

Таким образом, если для текущей вершины [math]v \ne root \, \exists[/math] непосредственный сын [math]v[/math]: [math]up[v] \ge tin[u][/math], то вершина [math]u[/math] является точкой сочленения; в противном случае она точкой сочленения не является.

Реализация

В массиве [math]answer[][/math] для каждой вершины содержится булево значение - является она точкой сочленения или нет. Изначально все значения false.

dfs[math](u, \, prev)[/math]
    [math]used[u] \leftarrow[/math]true
    [math]tin[u] \leftarrow time[/math]                          //задание времени входа в вершину u
    [math]up[u] \leftarrow time[/math]                          //задание начального значения up для вершины u
    [math]time \leftarrow time + 1[/math]
    [math]count \leftarrow 0[/math]                              //счетчик количества детей вершины u в дереве обхода
    for [math](v : uv \in E)[/math]
        if [math]v = prev[/math]
            continue
        if [math]used[v][/math]                            //v - предок вершины u, uv - обратное ребро
            [math]up[u] \leftarrow min(up[u], \, tin[v])[/math]
        else                                   //v - ребенок вершины u
            [math]count \leftarrow count + 1[/math]
            dfs[math](v, u)[/math]
            [math]up[u] \leftarrow min(up[u], \, up[v])[/math]
            if [math]up[v] \ge tin[u][/math]
                [math]answer[u] \leftarrow[/math]true           //не существует обратного ребра из вершины v или ее потомка в предка вершины u. вершина u - точка сочленения
    if [math]p = -1[/math]                               //является ли u корнем дерева обхода
        [math]answer[u] \leftarrow (count \gt  1)[/math];       //проверка количества детей у корня дерева

Источники

MAXimal::algo