Рубрики

Алгоритм Тарьяна для нахождения сильно связанных компонентов

Ориентированный граф сильно связен, если между всеми парами вершин существует путь. Сильно связная компонента ( SCC ) ориентированного графа является максимальным сильно связным подграфом. Например, на следующем графике есть 3 SCC.

Мы обсудили алгоритм Косараю для сильно связанных компонентов . Ранее рассмотренный алгоритм требует двух обходов графа DFS. В этом посте обсуждается алгоритм Тарьяна, который требует только одного обхода DFS.

Алгоритм Тарьяна основан на следующих фактах:
1. Поиск DFS создает дерево / лес DFS
2. Сильно связанные компоненты образуют поддеревья дерева DFS.
3. Если мы можем найти заголовок таких поддеревьев, мы можем напечатать / сохранить все узлы в этом поддереве (включая заголовок), и это будет один SCC.
4. Отсутствует задний край от одного SCC к другому (могут быть перекрестные края, но перекрестные края не будут использоваться при обработке графика).

Чтобы найти заголовок SCC, мы рассчитываем диск и нижний массив (как это сделано для точки сочленения , моста , двусвязного компонента ). Как обсуждалось в предыдущих постах, low [u] указывает на самую раннюю посещенную вершину (вершину с минимальным временем обнаружения), которая может быть достигнута из поддерева с корнем u. Узел u является головным, если disc [u] = low [u].

Ниже изображение является иллюстрацией подхода:

Сильно связанный компонент относится только к ориентированному графу, но значения Disc и Low относятся как к ориентированному, так и к ненаправленному графу, поэтому на рисунке выше мы взяли неориентированный граф.

На рисунке выше мы показали граф и его дерево DFS (на одном и том же графике могут быть разные деревья DFS в зависимости от порядка прохождения ребер).
В дереве DFS непрерывные стрелки — это ребра дерева, а пунктирные стрелки — это задние ребра (края дерева DFS
Значения Disc и Low показаны на рисунке для каждого узла как (Disc / Low).
Диск: Это время , когда узел посещается 1 — е время во время обхода DFS. Для узлов A, B, C, .., J в дереве DFS значениями Disc являются 1, 2, 3, .., 10.
Низкий: в дереве DFS ребра дерева переносят нас вперед от узла-предка к одному из его потомков. Например, из узла C ребра дерева могут привести нас к узлу G, узлу I и т. Д. Задние ребра ведут нас назад, от узла-потомка к одному из его предков. Например, из узла G обратные ребра приводят нас к E или C. Если мы посмотрим на дерево и задний край вместе, то мы можем видеть, что если мы начнем обход с одного узла, мы можем спуститься вниз по дереву через ребра дерева и затем поднимитесь через задние края. Например, из узла E мы можем спуститься до G, а затем подняться до C. Аналогично, из E мы можем спуститься до I или J и затем подняться до F. «Низкое» значение узла указывает на самый верхний достижимый предок (с минимально возможным значением Disc) через поддерево этого узла. Таким образом, для любого узла значение Low равно его значению Disc в любом случае (узел является предком самого себя). Затем мы смотрим в его поддерево и видим, есть ли какой-нибудь узел, который может привести нас к любому из его предков. Если в поддереве есть несколько обратных ребер, которые ведут нас к разным предкам, то мы берем тот, у которого минимальное значение Disc (то есть самый верхний). Если мы посмотрим на узел F, у него есть два поддерева. Поддерево с узлом G возвращает нас к E и C. Другое поддерево возвращает нас только к F. Здесь самым верхним предком является C, где F может достигать, и поэтому Низкое значение F равно 3 (Значение диска C).
Исходя из вышеприведенного обсуждения, должно быть ясно, что низкие значения B, C и D равны 1 (поскольку A является самым верхним узлом, в который могут попасть B, C и D). Таким же образом, низкие значения E, F, G равны 3, а низкие значения H, I, J равны 6.

Для любого узла u, когда запускается DFS, для Low будет установлен Disc 1 st .
Затем в дальнейшем DFS будет выполняться для каждого из его дочерних элементов v один за другим. Низкое значение u может изменить его в двух случаях:
Case1 (Tree Edge): если узел v еще не посещен, то после завершения DFS для v, минимум low [u] и low [v] будет обновлен до low [u].
низкий [u] = min (низкий [u], низкий [v]);
Случай 2 (Back Edge): когда дочерний элемент v уже посещен, тогда минимум low [u] и Disc [v] будут обновлены до low [u].
low [u] = min (low [u], disc [v]);
В случае два, можем ли мы взять low [v] вместо disc [v] ?? , Ответ НЕТ . Если вы можете подумать, почему ответ НЕТ , вы, вероятно, поняли концепцию Low и Disc.

Одинаковые значения Low и Disc помогают решать другие задачи графа, такие как точка сочленения , мост и двусвязный компонент .

Чтобы отследить поддерево с корнем в голове, мы можем использовать стек (продолжайте нажимать на узел во время посещения). Когда головной узел найден, вытолкните все узлы из стека, пока не выйдете из стека.

Чтобы убедиться, что мы не учитываем перекрестные границы, когда мы достигаем узла, который уже посещен, мы должны обрабатывать посещенный узел, только если он присутствует в стеке, иначе игнорировать узел.

Ниже приведена реализация алгоритма Тарьяна для печати всех ГТК.

C / C ++

// Программа на C ++ для поиска сильно связанных компонентов в данном
// направленный граф по алгоритму Тарьяна (одиночная DFS)
#include<iostream>
#include <list>
#include <stack>
#define NIL -1

using namespace std;

  
// Класс, представляющий ориентированный граф

class Graph

{

    int V;    // Количество вершин

    list<int> *adj;    // Динамический массив списков смежности

  

    // Рекурсивная DFS-функция, используемая SCC ()

    void SCCUtil(int u, int disc[], int low[],

                 stack<int> *st, bool stackMember[]);

public:

    Graph(int V);   // Конструктор

    void addEdge(int v, int w);   // функция для добавления ребра на график

    void SCC();    // печатает сильно связанные компоненты

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w);

}

  
// Рекурсивная функция, которая находит и печатает сильно связанные
// компоненты, использующие обход DFS
// u -> вершина, которую нужно посетить затем
// disc [] -> Хранит время обнаружения посещенных вершин
// low [] - >> самая ранняя посещенная вершина (вершина с минимальным
// время обнаружения), которое может быть достигнуто из поддерева
// корень с текущей вершиной
// * st - >> Для хранения всех подключенных предков (может быть частью
// ГТК)
// stackMember [] -> бит / индексный массив для быстрой проверки
// узел находится в стеке

void Graph::SCCUtil(int u, int disc[], int low[], stack<int> *st,

                    bool stackMember[])

{

    // Статическая переменная используется для простоты, мы можем избежать использования

    // статической переменной путем передачи указателя.

    static int time = 0;

  

    // Инициализация времени обнаружения и низкого значения

    disc[u] = low[u] = ++time;

    st->push(u);

    stackMember[u] = true;

  

    // Пройти через все вершины, смежные с этим

    list<int>::iterator i;

    for (i = adj[u].begin(); i != adj[u].end(); ++i)

    {

        int v = *i;  // v текущее смежное с 'u'

  

        // Если v еще не посещено, то повторить его

        if (disc[v] == -1)

        {

            SCCUtil(v, disc, low, st, stackMember);

  

            // Проверяем, имеет ли поддерево с корнем 'v'

            // соединение с одним из предков 'u'

            // Случай 1 (в приведенном выше обсуждении Disc и Low value)

            low[u]  = min(low[u], low[v]);

        }

  

        // Обновляем низкое значение 'u', только v остается в стеке

        // (т.е. это задний край, а не поперечный край).

        // Случай 2 (в приведенном выше обсуждении Disc и Low value)

        else if (stackMember[v] == true)

            low[u]  = min(low[u], disc[v]);

    }

  

    // найден головной узел, вытолкнуть стек и распечатать SCC

    int w = 0;  // Для хранения извлеченных в стеке вершин

    if (low[u] == disc[u])

    {

        while (st->top() != u)

        {

            w = (int) st->top();

            cout << w << " ";

            stackMember[w] = false;

            st->pop();

        }

        w = (int) st->top();

        cout << w << "\n";

        stackMember[w] = false;

        st->pop();

    }

}

  
// Функция для обхода DFS. Он использует SCCUtil ()

void Graph::SCC()

{

    int *disc = new int[V];

    int *low = new int[V];

    bool *stackMember = new bool[V];

    stack<int> *st = new stack<int>();

  

    // Инициализируем дисковые и низкие массивы и массивы stackMember

    for (int i = 0; i < V; i++)

    {

        disc[i] = NIL;

        low[i] = NIL;

        stackMember[i] = false;

    }

  

    // Вызываем рекурсивную вспомогательную функцию, чтобы найти сильно

    // связанные компоненты в дереве DFS с вершиной 'i'

    for (int i = 0; i < V; i++)

        if (disc[i] == NIL)

            SCCUtil(i, disc, low, st, stackMember);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    cout << "\nSCCs in first graph \n";

    Graph g1(5);

    g1.addEdge(1, 0);

    g1.addEdge(0, 2);

    g1.addEdge(2, 1);

    g1.addEdge(0, 3);

    g1.addEdge(3, 4);

    g1.SCC();

  

    cout << "\nSCCs in second graph \n";

    Graph g2(4);

    g2.addEdge(0, 1);

    g2.addEdge(1, 2);

    g2.addEdge(2, 3);

    g2.SCC();

  

    cout << "\nSCCs in third graph \n";

    Graph g3(7);

    g3.addEdge(0, 1);

    g3.addEdge(1, 2);

    g3.addEdge(2, 0);

    g3.addEdge(1, 3);

    g3.addEdge(1, 4);

    g3.addEdge(1, 6);

    g3.addEdge(3, 5);

    g3.addEdge(4, 5);

    g3.SCC();

  

    cout << "\nSCCs in fourth graph \n";

    Graph g4(11);

    g4.addEdge(0,1);g4.addEdge(0,3);

    g4.addEdge(1,2);g4.addEdge(1,4);

    g4.addEdge(2,0);g4.addEdge(2,6);

    g4.addEdge(3,2);

    g4.addEdge(4,5);g4.addEdge(4,6);

    g4.addEdge(5,6);g4.addEdge(5,7);g4.addEdge(5,8);g4.addEdge(5,9);

    g4.addEdge(6,4);

    g4.addEdge(7,9);

    g4.addEdge(8,9);

    g4.addEdge(9,8);

    g4.SCC();

  

    cout << "\nSCCs in fifth graph \n";

    Graph g5(5);

    g5.addEdge(0,1);

    g5.addEdge(1,2);

    g5.addEdge(2,3);

    g5.addEdge(2,4);

    g5.addEdge(3,0);

    g5.addEdge(4,2);

    g5.SCC();

  

    return 0;

}

питон

# Программа Python для поиска сильно связанных компонентов в заданном
# направленный граф по алгоритму Тарьяна (одиночная DFS)
# Сложность: O (V + E)

   

from collections import defaultdict

   
# Этот класс представляет ориентированный граф
# использование представления списка смежности

class Graph:

   

    def __init__(self,vertices):

        #No. вершин

        self.V= vertices 

          

        # словарь по умолчанию для хранения графика

        self.graph = defaultdict(list

          

        self.Time = 0

   

    # функция для добавления ребра на график

    def addEdge(self,u,v):

        self.graph[u].append(v)

          

   

    '' 'Рекурсивная функция, которая находит находки и печатает сильно связанные

    компоненты, использующие обход DFS

    u -> вершина, которую нужно посетить затем

    disc [] -> Хранит время обнаружения посещенных вершин

    low [] - >> самая ранняя посещенная вершина (вершина с минимальным

                время открытия), которое может быть достигнуто из поддерева

                коренится с текущей вершиной

     st - >> Для хранения всех подключенных предков (может быть частью

           ГТК)

     stackMember [] -> массив бит / индекс для более быстрой проверки

                  узел находится в стеке

    «»»

    def SCCUtil(self,u, low, disc, stackMember, st):

  

        # Инициализировать время обнаружения и низкое значение

        disc[u] = self.Time

        low[u] = self.Time

        self.Time += 1

        stackMember[u] = True

        st.append(u)

  

        # Пройдите все вершины, смежные с этим

        for v in self.graph[u]:

              

            # Если v еще не посещено, то повторить

            if disc[v] == -1 :

              

                self.SCCUtil(v, low, disc, stackMember, st)

  

                # Проверьте, подключено ли поддерево с корнем v

                # один из предков тебя

                # Случай 1 (согласно обсуждению выше по Диску и Низкому значению)

                low[u] = min(low[u], low[v])

                          

            elif stackMember[v] == True

  

                '' 'Обновлять низкое значение' u ', только если' v 'все еще в стеке

                (т.е. это задний край, а не поперечный край).

                Случай 2 (согласно обсуждению выше по Диску и Низкому значению) '' '

                low[u] = min(low[u], disc[v])

  

        # найден головной узел, вытолкните стек и распечатайте SCC

        w = -1 # Хранить в стеке извлеченные вершины

        if low[u] == disc[u]:

            while w != u:

                w = st.pop()

                print w,

                stackMember[w] = False

                  

            print""

              

      

  

    # Функция для выполнения обхода DFS.

    # Использует рекурсивный SCCUtil ()

    def SCC(self):

   

        # Отметить все вершины как не посещенные

        # и инициализировать родительский и посещенный,

        Массивы # и ap (точка сочленения)

        disc = [-1] * (self.V)

        low = [-1] * (self.V)

        stackMember = [False] * (self.V)

        st =[]

          

  

        # Вызовите рекурсивную вспомогательную функцию

        # найти точки сочленения

        # в дереве DFS с корнем из вершины 'i'

        for i in range(self.V):

            if disc[i] == -1:

                self.SCCUtil(i, low, disc, stackMember, st)

  

  

   

   

   
# Создайте график, приведенный на диаграмме выше

g1 = Graph(5)

g1.addEdge(1, 0)

g1.addEdge(0, 2)

g1.addEdge(2, 1)

g1.addEdge(0, 3)

g1.addEdge(3, 4)

print "SSC in first graph "

g1.SCC()

  

g2 = Graph(4)

g2.addEdge(0, 1)

g2.addEdge(1, 2)

g2.addEdge(2, 3)

print "nSSC in second graph "

g2.SCC()

  

   

g3 = Graph(7)

g3.addEdge(0, 1)

g3.addEdge(1, 2)

g3.addEdge(2, 0)

g3.addEdge(1, 3)

g3.addEdge(1, 4)

g3.addEdge(1, 6)

g3.addEdge(3, 5)

g3.addEdge(4, 5)

print "nSSC in third graph "

g3.SCC()

  

g4 = Graph(11)

g4.addEdge(0, 1)

g4.addEdge(0, 3)

g4.addEdge(1, 2)

g4.addEdge(1, 4)

g4.addEdge(2, 0)

g4.addEdge(2, 6)

g4.addEdge(3, 2)

g4.addEdge(4, 5)

g4.addEdge(4, 6)

g4.addEdge(5, 6)

g4.addEdge(5, 7)

g4.addEdge(5, 8)

g4.addEdge(5, 9)

g4.addEdge(6, 4)

g4.addEdge(7, 9)

g4.addEdge(8, 9)

g4.addEdge(9, 8)

print "nSSC in fourth graph "

g4.SCC();

  

  

g5 = Graph (5)

g5.addEdge(0, 1)

g5.addEdge(1, 2)

g5.addEdge(2, 3)

g5.addEdge(2, 4)

g5.addEdge(3, 0)

g5.addEdge(4, 2)

print "nSSC in fifth graph "

g5.SCC();

  
# Этот код предоставлен Ниламом Ядавом


Выход:

SCCs in first graph
4
3
1 2 0

SCCs in second graph
3
2
1
0

SCCs in third graph
5
3
4
6
2 1 0

SCCs in fourth graph
8 9
7
5 4 6
3 2 1 0
10

SCCs in fifth graph
4 3 2 1 0 

Сложность времени: вышеупомянутый алгоритм в основном вызывает DFS, DFS принимает O (V + E) для графа, представленного с использованием списка смежности.

Ссылки:
http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
http://www.ics.uci.edu/~eppstein/161/960220.html#sca

Эта статья предоставлена Анураг Сингх . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Алгоритм Тарьяна для нахождения сильно связанных компонентов

0.00 (0%) 0 votes