Двусвязный граф на Java

Двусвязный граф на Java

 

В теории графов двусвязный граф — это связный и неделимый граф, в том смысле, что удаление любой вершины не приведёт к потере связности. Таким образом, двусвязный граф не имеет шарниров.

Свойство вершинной 2-связности эквивалентно двусвязности с одним исключением — полный граф с двумя вершинами иногда считается двусвязным, но не вершинно-двусвязным.

Это свойство особенно полезно при рассмотрении графов с двойным резервированием, чтобы избежать разрыва при удалении единственного ребра.

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

Двусвязный неориентированный граф — это связный граф, не распадающийся на части при удалении любой вершины (и всех инцидентных ей рёбер).

Двусвязный ориентированный граф — это такой граф, что для любых двух вершин v и w имеется два ориентированных пути из v в w, не имеющих общих вершин кроме v и w.

Число вершинЧисло вариантов
Неделимые (или 2-связные) графы (или блоки) с n вершинами (последовательность A002218 в OEIS)
10
21
31
43
510
656
7468
87123
9194066
109743542
11900969091
12153620333545
1348432939150704
1428361824488394169
1530995890806033380784
1663501635429109597504951
17244852079292073376010411280
181783160594069429925952824734641
1924603887051350945867492816663958981

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

import java.util.*;
import java.util.stream.Stream;
public class Biconnectivity {
    List<Integer>[] graph;
    boolean[] visited;
    Stack<Integer> stack;
    int time;
    int[] tin;
    int[] lowlink;
    List<List<Integer>> edgeBiconnectedComponents;
    List<Integer> cutPoints;
    List<String> bridges;
    public List<List<Integer>> biconnectivity(List<Integer>[] graph) {
        int n = graph.length;
        this.graph = graph;
        visited = new boolean[n];
        stack = new Stack<>();
        time = 0;
        tin = new int[n];
        lowlink = new int[n];
        edgeBiconnectedComponents = new ArrayList<>();
        cutPoints = new ArrayList<>();
        bridges = new ArrayList<>();
        for (int u = 0; u < n; u++)
            if (!visited[u])
                dfs(u, -1);
        return edgeBiconnectedComponents;
    }
    void dfs(int u, int p) {
        visited[u] = true;
        lowlink[u] = tin[u] = time++;
        stack.add(u);
        int children = 0;
        boolean cutPoint = false;
        for (int v : graph[u]) {
            if (v == p)
                continue;
            if (visited[v]) {
                lowlink[u] = Math.min(lowlink[u], tin[v]); // or lowlink[u] = Math.min(lowlink[u], lowlink[v]);
            } else {
                dfs(v, u);
                lowlink[u] = Math.min(lowlink[u], lowlink[v]);
                cutPoint |=  tin[u] <= lowlink[v];
                if (tin[u] < lowlink[v]) // or if (lowlink[v] == tin[v])
                    bridges.add("(" + u + "," + v + ")");
                ++children;
            }
        }
        if (p == -1)
            cutPoint = children >= 2;
        if (cutPoint)
            cutPoints.add(u);
        if (tin[u] == lowlink[u]) {
            List<Integer> component = new ArrayList<>();
            while (true) {
                int x = stack.pop();
                component.add(x);
                if (x == u)
                    break;
            }
            edgeBiconnectedComponents.add(component);
        }
    }
    // tree of edge-biconnected components
    public static List<Integer>[] ebcTree(List<Integer>[] graph, List<List<Integer>> components) {
        int[] comp = new int[graph.length];
        for (int i = 0; i < components.size(); i++)
            for (int u : components.get(i))
                comp[u] = i;
        List<Integer>[] g = Stream.generate(ArrayList::new).limit(components.size()).toArray(List[]::new);
        for (int u = 0; u < graph.length; u++)
            for (int v : graph[u])
                if (comp[u] != comp[v])
                    g[comp[u]].add(comp[v]);
        return g;
    }
    // Usage example
    public static void main(String[] args) {
        List<Integer>[] graph = Stream.generate(ArrayList::new).limit(6).toArray(List[]::new);
        int[][] esges = {{0, 1}, {1, 2}, {0, 2}, {2, 3}, {1, 4}, {4, 5}, {5, 1}};
        for (int[] edge : esges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        Biconnectivity bc = new Biconnectivity();
        List<List<Integer>> components = bc.biconnectivity(graph);
        System.out.println("edge-biconnected components:" + components);
        System.out.println("cut points: " + bc.cutPoints);
        System.out.println("bridges:" + bc.bridges);
        System.out.println("condensation tree:" + Arrays.toString(ebcTree(graph, components)));
    }
}

57