Рубрики

Проверьте, сильно ли граф связан | Набор 1 (Косараю, используя DFS)

По заданному графу выяснить, является ли граф сильно связным или нет. Ориентированный граф сильно связен, если Между любыми двумя парами вершин есть путь. Например, следующий является сильно связным графом.

Это легко для неориентированного графа , мы можем просто сделать BFS и DFS, начиная с любой вершины. Если BFS или DFS посещает все вершины, то данный неориентированный граф связен. Этот подход не будет работать для ориентированного графа. Например, рассмотрим следующий граф, который не сильно связан. Если мы начнем DFS (или BFS) с вершины 0, мы сможем достичь всех вершин, но если мы начнем с любой другой вершины, мы не сможем достичь всех вершин.

Как сделать для ориентированного графа?

Простая идея состоит в том, чтобы использовать алгоритм кратчайшего пути из всех пар, такой как Флойд Варшалл, или найти транзитивное замыкание графа. Временная сложность этого метода будет O (v 3 ).

Мы также можем выполнить DFS V раз, начиная с каждой вершины. Если какая-либо DFS не посещает все вершины, то граф не сильно связан. Этот алгоритм занимает время O (V * (V + E)), которое может быть таким же, как транзитивное замыкание для плотного графа.

Лучшей идеей может быть алгоритм Сильно связанных компонентов (SCC) . Мы можем найти все ГТК за O (V + E) время. Если число SCCs одно, то граф сильно связен. Алгоритм для SCC выполняет дополнительную работу, так как находит все SCC.

Ниже приводится простой алгоритм Kosaraju, основанный на DFS, который выполняет два обхода графа DFS :
1) Инициализировать все вершины как не посещенные.

2) Выполните обход DFS графа, начиная с любой произвольной вершины v. Если обход DFS не посещает все вершины, верните false.

3) Инвертировать все дуги (или найти транспонирование или реверс графика)

4) Пометить все вершины как не посещенные в обратном графе.

5) Выполните обход DFS обратного графа, начиная с той же вершины v (то же, что и шаг 2). Если обход DFS не посещает все вершины, верните false. В противном случае верните истину.

Идея состоит в том, что если каждый узел может быть достигнут из вершины v, и каждый узел может достичь v, то граф сильно связан. На шаге 2 мы проверяем, достижимы ли все вершины из v. На шаге 4 мы проверяем, могут ли все вершины достичь v (в обратном графе, если все вершины достижимы из v, все вершины могут достичь v в исходном графе).

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для проверки, является ли данный ориентированный граф сильно
// подключен или нет
#include <iostream>
#include <list>
#include <stack>

using namespace std;

  

class Graph

{

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

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

  

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

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

public:

    // Конструктор и Деструктор

    Graph(int V) { this->V = V;  adj = new list<int>[V];}

    ~Graph() { delete [] adj; }

  

    // Метод добавления ребра

    void addEdge(int v, int w);

  

    // Основная функция, которая возвращает true, если граф сильно

    // подключен, иначе ложь

    bool isSC();

  

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

    Graph getTranspose();

};

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

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

{

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

    visited[v] = true;

  

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

    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.

}

  
// Основная функция, которая возвращает true, если граф сильно связан

bool Graph::isSC()

{

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

    bool visited[V];

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

        visited[i] = false;

  

    // Шаг 2: Выполнить обход DFS, начиная с первой вершины.

    DFSUtil(0, visited);

  

     // Если обход DFS не посещает все вершины, вернуть false.

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

        if (visited[i] == false)

             return false;

  

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

    Graph gr = getTranspose();

  

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

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

        visited[i] = false;

  

    // Шаг 5: сделать DFS для обратного графа, начиная с первой вершины.

    // Начинающая вершина должна быть той же отправной точкой первой DFS

    gr.DFSUtil(0, visited);

  

    // Если все вершины не посещены во второй DFS, то

    // вернуть ложь

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

        if (visited[i] == false)

             return false;

  

    return true;

}

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

int main()

{

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

    Graph g1(5);

    g1.addEdge(0, 1);

    g1.addEdge(1, 2);

    g1.addEdge(2, 3);

    g1.addEdge(3, 0);

    g1.addEdge(2, 4);

    g1.addEdge(4, 2);

    g1.isSC()? cout << "Yes\n" : cout << "No\n";

  

    Graph g2(4);

    g2.addEdge(0, 1);

    g2.addEdge(1, 2);

    g2.addEdge(2, 3);

    g2.isSC()? cout << "Yes\n" : cout << "No\n";

  

    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;

  

        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;

    }

  

    // Основная функция, которая возвращает true, если граф сильно

    // связано

    Boolean isSC()

    {

        // Шаг 1: Отметить все вершины как не посещенные

        // (для первой DFS)

        Boolean visited[] = new Boolean[V];

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

            visited[i] = false;

  

        // Шаг 2: Выполнить обход DFS, начиная с первой вершины.

        DFSUtil(0, visited);

  

        // Если обход DFS не посещает все вершины, то

        // вернуть false.

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

            if (visited[i] == false)

                return false;

  

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

        Graph gr = getTranspose();

  

        // Шаг 4: Отметить все вершины как не посещенные (Для

        // вторая DFS)

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

            visited[i] = false;

  

        // Шаг 5: сделать DFS для обратного графика, начиная с

        // первая вершина. Начинающая вершина должна быть одинаковой, начиная

        // точка первой DFS

        gr.DFSUtil(0, visited);

  

        // Если все вершины не посещены во второй DFS, то

        // вернуть ложь

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

            if (visited[i] == false)

                return false;

  

        return true;

    }

  

    public static void main(String args[])

    {

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

        Graph g1 = new Graph(5);

        g1.addEdge(0, 1);

        g1.addEdge(1, 2);

        g1.addEdge(2, 3);

        g1.addEdge(3, 0);

        g1.addEdge(2, 4);

        g1.addEdge(4, 2);

        if (g1.isSC())

            System.out.println("Yes");

        else

            System.out.println("No");

  

        Graph g2 = new Graph(4);

        g2.addEdge(0, 1);

        g2.addEdge(1, 2);

        g2.addEdge(2, 3);

        if (g2.isSC())

            System.out.println("Yes");

        else

            System.out.println("No");

    }

}
// Этот код предоставлен 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)

      

   

    # Функция, используемая isSC () для выполнения DFS

    def DFSUtil(self,v,visited):

  

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

        visited[v]= True

  

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

        for i in self.graph[v]:

            if visited[i]==False:

                self.DFSUtil(i,visited)

  

  

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

    def getTranspose(self):

  

        g = Graph(self.V)

  

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

        for i in self.graph:

            for j in self.graph[i]:

                g.addEdge(j,i)

          

        return g

  

          

    # Основная функция, которая возвращает true, если граф сильно связан

    def isSC(self):

  

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

        visited =[False]*(self.V)

          

        # Шаг 2: Выполнить обход DFS, начиная с первой вершины.

        self.DFSUtil(0,visited)

  

        # Если обход DFS не посещает все вершины, вернуть false

        if any(i == False for i in visited):

            return False

  

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

        gr = self.getTranspose()

          

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

        visited =[False]*(self.V)

  

        # Шаг 5: Сделать DFS для обратного графа, начиная с первой вершины.

        # Начинающая вершина должна быть той же отправной точкой первой DFS

        gr.DFSUtil(0,visited)

  

        # Если все вершины не посещены во второй DFS, то

        # вернуть ложь

        if any(i == False for i in visited):

            return False

  

        return True

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

g1 = Graph(5)

g1.addEdge(0, 1)

g1.addEdge(1, 2)

g1.addEdge(2, 3)

g1.addEdge(3, 0)

g1.addEdge(2, 4)

g1.addEdge(4, 2)

print "Yes" if g1.isSC() else "No"

  

g2 = Graph(4)

g2.addEdge(0, 1)

g2.addEdge(1, 2)

g2.addEdge(2, 3)

print "Yes" if g2.isSC() else "No"

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


Выход:

Yes
No

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

Можем ли мы улучшить дальше?
Вышеупомянутый подход требует двух обходов графа. Мы можем определить, является ли граф сильно связанным или нет в одном обходе, используя алгоритм Тарьяна для поиска сильно связанных компонентов .

Упражнение:
Можем ли мы использовать BFS вместо DFS в приведенном выше алгоритме? Смотрите это .

Ссылки:
http://www.ieor.berkeley.edu/~hochbaum/files/ieor266-2012.pdf

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

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

Проверьте, сильно ли граф связан | Набор 1 (Косараю, используя DFS)

0.00 (0%) 0 votes