Рубрики

Сильно связанные компоненты

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

Мы можем найти все сильно связанные компоненты за O (V + E) время, используя алгоритм Косараю . Ниже приводится подробный алгоритм Косараю.
1) Создайте пустой стек 'S' и выполните обход DFS графа. При обходе DFS, после вызова рекурсивной DFS для смежных вершин вершины, поместите вершину в стек. На приведенном выше графике, если мы запускаем DFS с вершины 0, мы получаем вершины в стеке как 1, 2, 4, 3, 0.
2) Обратные направления всех дуг для получения транспонированного графа.
3) Один за другим вытолкнуть вершину из S, пока S не пусто. Пусть вытянутая вершина будет 'v'. Возьмите v как источник и сделайте DFS (вызовите DFSUtil (v) ). DFS, начиная с v, печатает сильно связную компоненту v. В приведенном выше примере мы обрабатываем вершины в порядке 0, 3, 4, 2, 1 (один за другим выскочил из стека).

Как это работает?
Вышеприведенный алгоритм основан на DFS. Это делает DFS два раза. DFS графа создает одно дерево, если все вершины достижимы с начальной точки DFS. В противном случае DFS создает лес. Таким образом, DFS графа с одним SCC всегда создает дерево. Важно отметить, что DFS может создавать дерево или лес, если имеется более одного SCC в зависимости от выбранной начальной точки. Например, на диаграмме выше, если мы запускаем DFS с вершин 0 или 1 или 2, мы получаем дерево в качестве вывода. И если мы начнем с 3 или 4, мы получим лес. Чтобы найти и распечатать все SCC, мы хотели бы запустить DFS из вершины 4 (которая является вершиной приемника), затем перейти к 3, который является приемником в оставшемся множестве (набор исключает 4) и, наконец, в любую из оставшихся вершин (0, 1, 2). Итак, как мы можем найти эту последовательность выбора вершин в качестве отправной точки DFS? К сожалению, нет прямого способа получить эту последовательность. Однако, если мы выполняем DFS графа и храним вершины в соответствии с их временем окончания, мы гарантируем, что время окончания вершины, которая соединяется с другими SCC (кроме ее собственного SCC), всегда будет больше, чем время окончания вершин в другом ГТК (см. это для доказательства). Например, в DFS приведенного выше примера графа время окончания 0 всегда больше, чем 3 и 4 (независимо от последовательности вершин, рассматриваемой для DFS). И время окончания 3 всегда больше 4. DFS не гарантирует других вершин, например, время окончания 1 и 2 может быть меньше или больше 3 и 4 в зависимости от последовательности вершин, рассматриваемой для DFS. Поэтому, чтобы использовать это свойство, мы выполняем DFS-обход полного графа и помещаем каждую законченную вершину в стек. В стеке 3 всегда появляется после 4, а 0 появляется после 3 и 4.
На следующем шаге мы перевернем график. Рассмотрим график ГТК. На перевернутом графике ребра, соединяющие два компонента, перевернуты. Таким образом, SCC {0, 1, 2} становится приемником, а SCC {4} становится источником. Как обсуждалось выше, в стеке у нас всегда 0 перед 3 и 4. Поэтому, если мы выполняем DFS обратного графа, используя последовательность вершин в стеке, мы обрабатываем вершины из приемника в источник (в обратном графе). Это то, чего мы хотели достичь, и это все, что нужно для печати ГТК один за другим.

Ниже приведена реализация алгоритма Косараю на C ++.

C ++

// C ++ Реализация алгоритма Косараю для печати всех ГТК
#include <iostream>
#include <list>
#include <stack>

using namespace std;

  

class Graph

{

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

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

  

    // Заполняет стек вершинами (в порядке увеличения

    // раз). Верхний элемент стека имеет максимальную отделку

    // время

    void fillOrder(int v, bool visited[], stack<int> &Stack);

  

    // Рекурсивная функция для печати DFS, начиная с v

    void DFSUtil(int v, bool visited[]);

public:

    Graph(int V);

    void addEdge(int v, int w);

  

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

    // компоненты

    void printSCCs();

  

    // Функция, которая возвращает реверс (или транспонирование) этого графа

    Graph getTranspose();

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  
// Рекурсивная функция для печати DFS, начиная с v

void Graph::DFSUtil(int v, bool visited[])

{

    // Пометить текущий узел как посещенный и распечатать его

    visited[v] = true;

    cout << v << " ";

  

    // Повторение для всех вершин, смежных с этой вершиной

    list<int>::iterator i;

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

        if (!visited[*i])

            DFSUtil(*i, visited);

}

  
Graph Graph::getTranspose()
{

    Graph g(V);

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

    {

        // Повторение для всех вершин, смежных с этой вершиной

        list<int>::iterator i;

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

        {

            g.adj[*i].push_back(v);

        }

    }

    return g;

}

  

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

{

    adj[v].push_back(w); // Добавить w в список v.

}

  

void Graph::fillOrder(int v, bool visited[], stack<int> &Stack)

{

    // Пометить текущий узел как посещенный и распечатать его

    visited[v] = true;

  

    // Повторение для всех вершин, смежных с этой вершиной

    list<int>::iterator i;

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

        if(!visited[*i])

            fillOrder(*i, visited, Stack);

  

    // Все вершины, доступные из v, уже обработаны, нажимаем v

    Stack.push(v);

}

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

void Graph::printSCCs()

{

    stack<int> Stack;

  

    // Пометить все вершины как не посещенные (для первой DFS)

    bool *visited = new bool[V];

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

        visited[i] = false;

  

    // Заполняем вершины в стеке согласно их времени окончания

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

        if(visited[i] == false)

            fillOrder(i, visited, Stack);

  

    // Создать перевернутый график

    Graph gr = getTranspose();

  

    // Пометить все вершины как не посещенные (для второго DFS)

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

        visited[i] = false;

  

    // Теперь обрабатываем все вершины в порядке, определенном стеком

    while (Stack.empty() == false)

    {

        // извлекаем вершину из стека

        int v = Stack.top();

        Stack.pop();

  

        // Распечатать Сильно связанный компонент вытянутой вершины

        if (visited[v] == false)

        {

            gr.DFSUtil(v, visited);

            cout << endl;

        }

    }

}

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

int main()

{

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

    Graph g(5);

    g.addEdge(1, 0);

    g.addEdge(0, 2);

    g.addEdge(2, 1);

    g.addEdge(0, 3);

    g.addEdge(3, 4);

  

    cout << "Following are strongly connected components in "

            "given graph \n";

    g.printSCCs();

  

    return 0;

}

Джава

// Java реализация алгоритма Косараю для печати всех ГТК

import java.io.*;

import java.util.*;

import java.util.LinkedList;

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

class Graph

{

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

    private LinkedList<Integer> adj[]; // Список смежности

  

    //Конструктор

    Graph(int v)

    {

        V = v;

        adj = new LinkedList[v];

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

            adj[i] = new LinkedList();

    }

  

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

    void addEdge(int v, int w)  { adj[v].add(w); }

  

    // Рекурсивная функция для печати DFS, начиная с v

    void DFSUtil(int v,boolean visited[])

    {

        // Пометить текущий узел как посещенный и распечатать его

        visited[v] = true;

        System.out.print(v + " ");

  

        int n;

  

        // Повторение для всех вершин, смежных с этой вершиной

        Iterator<Integer> i =adj[v].iterator();

        while (i.hasNext())

        {

            n = i.next();

            if (!visited[n])

                DFSUtil(n,visited);

        }

    }

  

    // Функция, которая возвращает реверс (или транспонирование) этого графа

    Graph getTranspose()

    {

        Graph g = new Graph(V);

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

        {

            // Повторение для всех вершин, смежных с этой вершиной

            Iterator<Integer> i =adj[v].listIterator();

            while(i.hasNext())

                g.adj[i.next()].add(v);

        }

        return g;

    }

  

    void fillOrder(int v, boolean visited[], Stack stack)

    {

        // Пометить текущий узел как посещенный и распечатать его

        visited[v] = true;

  

        // Повторение для всех вершин, смежных с этой вершиной

        Iterator<Integer> i = adj[v].iterator();

        while (i.hasNext())

        {

            int n = i.next();

            if(!visited[n])

                fillOrder(n, visited, stack);

        }

  

        // Все вершины, доступные из v, уже обработаны,

        // толкаем v в стек

        stack.push(new Integer(v));

    }

  

    // Основная функция, которая находит и печатает все сильно

    // подключенные компоненты

    void printSCCs()

    {

        Stack stack = new Stack();

  

        // Пометить все вершины как не посещенные (для первой DFS)

        boolean visited[] = new boolean[V];

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

            visited[i] = false;

  

        // Заполняем вершины в стеке в соответствии с их окончанием

        // раз

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

            if (visited[i] == false)

                fillOrder(i, visited, stack);

  

        // Создать перевернутый график

        Graph gr = getTranspose();

  

        // Пометить все вершины как не посещенные (для второго DFS)

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

            visited[i] = false;

  

        // Теперь обрабатываем все вершины в порядке, определенном стеком

        while (stack.empty() == false)

        {

            // извлекаем вершину из стека

            int v = (int)stack.pop();

  

            // Распечатать Сильно связанный компонент вытянутой вершины

            if (visited[v] == false)

            {

                gr.DFSUtil(v, visited);

                System.out.println();

            }

        }

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

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

        Graph g = new Graph(5);

        g.addEdge(1, 0);

        g.addEdge(0, 2);

        g.addEdge(2, 1);

        g.addEdge(0, 3);

        g.addEdge(3, 4);

  

        System.out.println("Following are strongly connected components "+

                           "in given graph ");

        g.printSCCs();

    }

}
// Этот код предоставлен Aakash Hasija

питон

# Python-реализация алгоритма Косараю для печати всех ГТК

  

from collections import defaultdict

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

class Graph:

   

    def __init__(self,vertices):

        self.V= vertices #No. вершин

        self.graph = defaultdict(list) # словарь по умолчанию для хранения графика

   

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

    def addEdge(self,u,v):

        self.graph[u].append(v)

   

    # Функция, используемая DFS

    def DFSUtil(self,v,visited):

        # Отметить текущий узел как посещенный и распечатать его

        visited[v]= True

        print v,

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

        for i in self.graph[v]:

            if visited[i]==False:

                self.DFSUtil(i,visited)

  

  

    def fillOrder(self,v,visited, stack):

        # Отметить текущий узел как посещенный

        visited[v]= True

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

        for i in self.graph[v]:

            if visited[i]==False:

                self.fillOrder(i, visited, stack)

        stack = stack.append(v)

      

  

    # Функция, которая возвращает реверс (или транспонирование) этого графа

    def getTranspose(self):

        g = Graph(self.V)

  

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

        for i in self.graph:

            for j in self.graph[i]:

                g.addEdge(j,i)

        return g

  

   

   

    # Основная функция, которая находит и печатает все сильно

    # подключенные компоненты

    def printSCCs(self):

          

         stack = []

        # Отметить все вершины как не посещенные (для первой DFS)

        visited =[False]*(self.V)

        # Заполните вершины в стеке в соответствии с их окончанием

        # раз

        for i in range(self.V):

            if visited[i]==False:

                self.fillOrder(i, visited, stack)

  

        # Создать перевернутый график

         gr = self.getTranspose()

           

         # Отметить все вершины как не посещенные (для второго DFS)

         visited =[False]*(self.V)

  

         # Теперь обрабатываем все вершины в порядке, определенном стеком

         while stack:

             i = stack.pop()

             if visited[i]==False:

                gr.DFSUtil(i, visited)

                print""

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

g = Graph(5)

g.addEdge(1, 0)

g.addEdge(0, 2)

g.addEdge(2, 1)

g.addEdge(0, 3)

g.addEdge(3, 4)

  

   

print ("Following are strongly connected components " +

                           "in given graph")

g.printSCCs()
# Этот код предоставлен Ниламом Ядавом


Выход:

Following are strongly connected components in given graph
0 1 2
3
4

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

Вышеупомянутый алгоритм является асимптотически лучшим алгоритмом, но есть другие алгоритмы, такие как алгоритм Тарьяна и основанный на пути, которые имеют одинаковую сложность по времени, но находят SCC, используя одну DFS. Алгоритм Тарьяна обсуждается в следующем посте.

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

Приложения:
Алгоритмы SCC могут использоваться в качестве первого шага во многих графовых алгоритмах, которые работают только на сильно связном графе.
В социальных сетях группа людей, как правило, тесно связана (например, ученики класса или любого другого общего места). Многие люди в этих группах, как правило, любят некоторые общие страницы или играют в обычные игры. Алгоритмы SCC могут быть использованы для поиска таких групп и предложения наиболее популярных страниц или игр людям в группе, которым еще не понравилась страница, которой обычно нравились, или которые играли в игру.

Ссылки:
http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
https://www.youtube.com/watch?v=PZQ0Pdk15RA

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

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

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

Сильно связанные компоненты

0.00 (0%) 0 votes