Рубрики

Двухсвязные компоненты

Двусвязный компонент является максимальным двусвязным подграфом .

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

На приведенном выше графике ниже приведены двусвязные компоненты:

  • 4–2 3–4 3–1 2–3 1–2
  • 8-9
  • 8–5 7–8 5–7
  • 6–0 5–6 1–5 0–1
  • 10-11

Алгоритм основан на Disc и Low Values, которые обсуждаются в статье « Сильно связанные компоненты» .

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

C ++

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

using namespace std;

int count = 0;

class Edge {

public:

    int u;

    int v;

    Edge(int u, int v);

};

Edge::Edge(int u, int v)

{

    this->u = u;

    this->v = v;

}

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

class Graph {

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

    int E; // Количество ребер

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

  

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

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

                 list<Edge>* st, int parent[]);

  

public:

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

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

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

};

  

Graph::Graph(int V)

{

    this->V = V;

    this->E = 0;

    adj = new list<int>[V];

}

  

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

{

    adj[v].push_back(w);

    E++;

}

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

void Graph::BCCUtil(int u, int disc[], int low[], list<Edge>* st,

                    int parent[])

{

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

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

    static int time = 0;

  

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

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

    int children = 0;

  

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

    list<int>::iterator i;

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

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

  

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

        if (disc[v] == -1) {

            children++;

            parent[v] = u;

            // сохраняем ребро в стеке

            st->push_back(Edge(u, v));

            BCCUtil(v, disc, low, st, parent);

  

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

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

            // Случай 1 - для статьи с сильно связанными компонентами

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

  

            // Если вы точка сочленения,

            // выталкиваем все ребра из стека до u - v

            if ((disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u])) {

                while (st->back().u != u || st->back().v != v) {

                    cout << st->back().u << "--" << st->back().v << " ";

                    st->pop_back();

                }

                cout << st->back().u << "--" << st->back().v;

                st->pop_back();

                cout << endl;

                count++;

            }

        }

  

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

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

        // Случай 2 - для статьи с сильно связанными компонентами

        else if (v != parent[u]) {

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

            if (disc[v] < disc[u]) {

                st->push_back(Edge(u, v));

            }

        }

    }

}

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

void Graph::BCC()

{

    int* disc = new int[V];

    int* low = new int[V];

    int* parent = new int[V];

    list<Edge>* st = new list<Edge>[E];

  

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

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

        disc[i] = NIL;

        low[i] = NIL;

        parent[i] = NIL;

    }

  

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

        if (disc[i] == NIL)

            BCCUtil(i, disc, low, st, parent);

  

        int j = 0;

        // Если стек не пустой, вытолкнуть все ребра из стека

        while (st->size() > 0) {

            j = 1;

            cout << st->back().u << "--" << st->back().v << " ";

            st->pop_back();

        }

        if (j == 1) {

            cout << endl;

            count++;

        }

    }

}

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

int main()

{

    Graph g(12);

    g.addEdge(0, 1);

    g.addEdge(1, 0);

    g.addEdge(1, 2);

    g.addEdge(2, 1);

    g.addEdge(1, 3);

    g.addEdge(3, 1);

    g.addEdge(2, 3);

    g.addEdge(3, 2);

    g.addEdge(2, 4);

    g.addEdge(4, 2);

    g.addEdge(3, 4);

    g.addEdge(4, 3);

    g.addEdge(1, 5);

    g.addEdge(5, 1);

    g.addEdge(0, 6);

    g.addEdge(6, 0);

    g.addEdge(5, 6);

    g.addEdge(6, 5);

    g.addEdge(5, 7);

    g.addEdge(7, 5);

    g.addEdge(5, 8);

    g.addEdge(8, 5);

    g.addEdge(7, 8);

    g.addEdge(8, 7);

    g.addEdge(8, 9);

    g.addEdge(9, 8);

    g.addEdge(10, 11);

    g.addEdge(11, 10);

    g.BCC();

    cout << "Above are " << count << " biconnected components in graph";

    return 0;

}

Джава

// Java-программа для поиска двусвязных компонентов в заданном
// неориентированный граф

import java.io.*;

import java.util.*;

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

class Graph {

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

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

  

    // Количество - это число двусвязных компонентов. время - это

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

    static int count = 0, time = 0;

  

    class Edge {

        int u;

        int v;

        Edge(int u, int v)

        {

            this.u = u;

            this.v = v;

        }

    };

  

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

    Graph(int v)

    {

        V = v;

        E = 0;

        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);

        E++;

    }

  

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

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

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

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

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

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

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

    // * st - >> Для сохранения посещенных ребер

    void BCCUtil(int u, int disc[], int low[], LinkedList<Edge> st,

                 int parent[])

    {

  

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

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

        int children = 0;

  

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

        Iterator<Integer> it = adj[u].iterator();

        while (it.hasNext()) {

            int v = it.next(); // v текущее смежное с 'u'

  

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

            if (disc[v] == -1) {

                children++;

                parent[v] = u;

  

                // сохраняем ребро в стеке

                st.add(new Edge(u, v));

                BCCUtil(v, disc, low, st, parent);

  

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

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

                // Случай 1 - для статьи с сильно связанными компонентами

                if (low[u] > low[v])

                    low[u] = low[v];

  

                // Если вы точка сочленения,

                // выталкиваем все ребра из стека до u - v

                if ((disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u])) {

                    while (st.getLast().u != u || st.getLast().v != v) {

                        System.out.print(st.getLast().u + "--" + st.getLast().v + " ");

                        st.removeLast();

                    }

                    System.out.println(st.getLast().u + "--" + st.getLast().v + " ");

                    st.removeLast();

  

                    count++;

                }

            }

  

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

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

            // Случай 2 - для статьи с сильно связанными компонентами

            else if (v != parent[u] && disc[v] < disc[u] ) {

                if (low[u] > disc[v])

                    low[u] = disc[v];

  

                st.add(new Edge(u, v));

            }

        }

    }

  

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

    void BCC()

    {

        int disc[] = new int[V];

        int low[] = new int[V];

        int parent[] = new int[V];

        LinkedList<Edge> st = new LinkedList<Edge>();

  

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

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

            disc[i] = -1;

            low[i] = -1;

            parent[i] = -1;

        }

  

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

            if (disc[i] == -1)

                BCCUtil(i, disc, low, st, parent);

  

            int j = 0;

  

            // Если стек не пустой, вытолкнуть все ребра из стека

            while (st.size() > 0) {

                j = 1;

                System.out.print(st.getLast().u + "--" + st.getLast().v + " ");

                st.removeLast();

            }

            if (j == 1) {

                System.out.println();

                count++;

            }

        }

    }

  

    public static void main(String args[])

    {

        Graph g = new Graph(12);

        g.addEdge(0, 1);

        g.addEdge(1, 0);

        g.addEdge(1, 2);

        g.addEdge(2, 1);

        g.addEdge(1, 3);

        g.addEdge(3, 1);

        g.addEdge(2, 3);

        g.addEdge(3, 2);

        g.addEdge(2, 4);

        g.addEdge(4, 2);

        g.addEdge(3, 4);

        g.addEdge(4, 3);

        g.addEdge(1, 5);

        g.addEdge(5, 1);

        g.addEdge(0, 6);

        g.addEdge(6, 0);

        g.addEdge(5, 6);

        g.addEdge(6, 5);

        g.addEdge(5, 7);

        g.addEdge(7, 5);

        g.addEdge(5, 8);

        g.addEdge(8, 5);

        g.addEdge(7, 8);

        g.addEdge(8, 7);

        g.addEdge(8, 9);

        g.addEdge(9, 8);

        g.addEdge(10, 11);

        g.addEdge(11, 10);

  

        g.BCC();

  

        System.out.println("Above are " + g.count + " biconnected components in graph");

    }

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

питон

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

  

   

from collections import defaultdict

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

class Graph:

   

    def __init__(self, vertices):

        # Количество вершин

        self.V = vertices 

          

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

        self.graph = defaultdict(list)

          

        # время используется, чтобы найти время обнаружения

        self.Time = 0 

          

        # Количество - это число двусвязных компонентов

        self.count = 0 

   

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

    def addEdge(self, u, v):

        self.graph[u].append(v) 

         self.graph[v].append(u)

  

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

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

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

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

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

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

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

    st - >> Хранить посещенные края '' '

    def BCCUtil(self, u, parent, low, disc, st):

  

        # Количество детей в текущем узле

        children = 0

  

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

        disc[u] = self.Time

        low[u] = self.Time

        self.Time += 1

  

  

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

        for v in self.graph[u]:

            # Если v еще не посещено, сделайте его потомком

            # в дереве DFS и повторить его

            if disc[v] == -1 :

                parent[v] = u

                children += 1

                st.append((u, v)) # сохранить ребро в стеке

                self.BCCUtil(v, parent, low, disc, st)

  

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

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

                # Случай 1 - на статью «Сильно связанные компоненты»

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

  

                # Если вы точка сочленения, поп

                # все ребра от стека до (u, v)

                if parent[u] == -1 and children > 1 or parent[u] != -1 and low[v] >= disc[u]:

                    self.count += 1 # количество приращений

                    w = -1

                    while w != (u, v):

                        w = st.pop()

                        print w,

                    print""

              

            elif v != parent[u] and low[u] > disc[v]:

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

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

                Дело 2

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

  

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

      

                st.append((u, v))

  

  

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

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

    def BCC(self):

          

        # Инициализировать дисковые и низкие и родительские массивы

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

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

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

        st = []

  

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

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

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

        for i in range(self.V):

            if disc[i] == -1:

                self.BCCUtil(i, parent, low, disc, st)

  

            # Если стек не пустой, вытолкните все ребра из стека

            if st:

                self.count = self.count + 1

  

                while st:

                    w = st.pop()

                    print w,

                print ""

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

  

g = Graph(12)

g.addEdge(0, 1)

g.addEdge(1, 2)

g.addEdge(1, 3)

g.addEdge(2, 3)

g.addEdge(2, 4)

g.addEdge(3, 4)

g.addEdge(1, 5)

g.addEdge(0, 6)

g.addEdge(5, 6)

g.addEdge(5, 7)

g.addEdge(5, 8)

g.addEdge(7, 8)

g.addEdge(8, 9)

g.addEdge(10, 11)

  
g.BCC();

print ("Above are % d biconnected components in graph" %(g.count));

  
# Этот код предоставлен Neelam Yadav

Выход:

4--2 3--4 3--1 2--3 1--2
8--9
8--5 7--8 5--7
6--0 5--6 1--5 0--1 
10--11
Above are 5 biconnected components in graph

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

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

Двухсвязные компоненты

0.00 (0%) 0 votes