Поиск компонент сильной связности в орграфе (реализация на Java)

Java   12 Июнь 2015  Автор статьи: admin 

Задан ориентированный граф, состоящий из N вершин и M дуг. Исходный орграф задается списком дуг. Требуется выделить в орграфе компоненты сильной связности.

Для решения данной задачи исходный орграф G удобно представлять в памяти ЭВМ списком смежности adj, храня для каждой вершины графа v список adj[v] смежных с ней вершин. Транспонированный орграф adjT также представляется в памяти ЭВМ списком смежности. Булевский массив used служит для отметки о том, стала вершина v посещенной в процессе обходов орграфа или еще нет. Топологически упорядоченная перестановка номеров вершин орграфа хранится при помощи списка topSort. Для принадлежности вершины к той или иной компоненте связности используется массив component. Количество компонент связности в орграфе хранится в переменной componentCount.

1
2
3
4
5
6
7
8
9
10
11
12
//список смежности орграфа
private ArrayList<Integer> adj[];
//список смежности транспонированного орграфа
private ArrayList<Integer> adjT[];
//массив для хранения информации о пройденных и не пройденных вершинах
private boolean used[];
//массив для хранения информации о пройденных и не пройденных вершинах
ArrayList<Integer> topSort;
//массив для обозначения компонент сильной связности орграфа
private int[] component;
//количество компонент связности в орграфе
int componentCount;

В качестве списка смежности для представления орграфа и транспонированного орграфа на языке Java удобно использовать массив, каждый элемент которого является структурой данных ArrayList<Integer>.
В приведенной ниже реализации данные считываются и выводятся в консоль.

Входные данные

В первой строке входного файла задано два целых числа: N (1 \le N \le 10^5) – количество вершин в орграфе и M (1 \le M \le 10^6) – количество дуг орграфа соответственно. Каждая из следующих M строк содержит описание дуги орграфа – два целых числа из диапазона от 1 до N, номер начала и конца дуги соответственно.

Выходные данные

На первой строке выходного файла выводится число L — количество компонент сильной связности заданного орграфа. На следующей строке выводится N чисел из диапазона от 1 до L — номера компонент сильной связности, которым принадлежат соответствующие вершины. Компоненты сильной связности нумеруются от 1 до L в топологическом порядке в конденсации заданного орграфа.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
   
    private int n; //количество вершин в орграфе
    private int m; //количество дуг в орграфе
    //список смежности орграфа
    private ArrayList<Integer> adj[];
    //список смежности транспонированного орграфа
    private ArrayList<Integer> adjT[];
    //массив для хранения информации о пройденных и не пройденных вершинах
    private boolean used[];
    //массив для хранения информации о пройденных и не пройденных вершинах
    ArrayList<Integer> topSort;
    private int[] component; //массив для обозначения компонент сильной связности орграфа
    int componentCount; //количество компонент связности в орграфе
   
    private BufferedReader cin;
    private PrintWriter cout;
    private StringTokenizer tokenizer;
   
    //процедура обхода в глубину
    private void dfs(int v) {
        //если вершина является пройденной, то не производим из нее вызов процедуры
        if (used[v]) {
            return;
        }
        used[v] = true; //помечаем вершину как пройденную
        //запускаем обход из всех вершин, смежных с вершиной v
        for (int i = 0; i < adj[v].size(); ++i) {
            int w = adj[v].get(i);
            dfs(w); //вызов обхода в глубину от вершины w, смежной с вершиной v
        }
        //добавляем посещенную вершину в топологический порядок
        topSort.add(v);
    }
   
    //процедура поиска компонент сильной связности орграфа
    private void ccs(int v, int componentID) {
        //если вершина является пройденной, то не производим из нее вызов процедуры
        if (used[v]) {
            return;
        }
        used[v] = true; //помечаем вершину как пройденную
        component[v] = componentID;
        //запускаем обход из всех вершин, смежных с вершиной v
        for (int i = 0; i < adjT[v].size(); ++i) {
            int w = adjT[v].get(i);
            ccs(w, componentID); //вызов обхода в глубину от вершины w, смежной с вершиной v в транспонированном графе
        }
    }
   
    //процедура считывания входных данных с консоли
    private void readData() throws IOException {
        cin = new BufferedReader(new InputStreamReader(System.in));
        cout = new PrintWriter(System.out);
       
        tokenizer = new StringTokenizer(cin.readLine());
        n = Integer.parseInt(tokenizer.nextToken()); //считываем количество вершин графа
        m = Integer.parseInt(tokenizer.nextToken()); //считываем количество ребер графа
       
        //инициализируем список смежности графа и транспонированного графа
        adj = new ArrayList[n];
        adjT = new ArrayList[n];
        for (int i = 0; i < n; ++i) {
            adj[i] = new ArrayList<Integer>();
            adjT[i] = new ArrayList<Integer>();
        }
       
        //считываем граф, заданный списком дуг
        for (int i = 0; i < m; ++i) {
            tokenizer = new StringTokenizer(cin.readLine());
            int v = Integer.parseInt(tokenizer.nextToken());
            int w = Integer.parseInt(tokenizer.nextToken());
            v--;
            w--;
            adj[v].add(w);
            //добавляем обратную дугу в транспонированный граф
            adjT[w].add(v);
        }
       
        //помечаем все вершины, как непосещенные
        used = new boolean[n];
        Arrays.fill(used, false);
       
        component = new int[n];
        Arrays.fill(component, 0);
       
        topSort = new ArrayList<Integer>();
    }
   
    //процедура вывода данных в консоль
    private void printData() throws IOException {
       
        cout.println(componentCount);
        for (int i = 0; i < n; ++i) {
            cout.print((component[i] + 1) + " ");
        }
        cout.println();
       
        cin.close();
        cout.close();
    }
   
    private void run() throws IOException {
        readData();
        //запускаем обход в глубину для расчета времени выхода каждой вершины
        for (int v = 0; v < n; ++v) {
            dfs(v);
        }
       
        //запускаем процедуру поиска компонент сильной связности в порядке уменьшения времени выхода вершин
        Arrays.fill(used, false);
        int componentID = 0;
        for (int i = topSort.size() - 1; i >= 0; --i) {
            int v = topSort.get(i);
            if (!used[v]) {
                ccs(v, componentID);
                componentID++;
            }
        }
        componentCount = componentID;
        printData();
    }
   
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        solution.run();
    }
}

 

Пример

Рассмотрим работу алгоритма на графе G, изображенном на рисунке.

орграф

В орграфе G существует четыре компоненты сильной связности.

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

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

конденсация

Входные данные
12 19
1 2
2 3
3 1
3 12
4 2
4 3
4 5
5 6
6 4
7 5
7 8
7 9
8 6
8 7
8 12
9 10
10 11
11 12
12 9
Выходные данные
4
3 3 3 2 2 2 1 1 4 4 4 4

 

Научиться программировать

  • на Delphi

  • на Java

  • на C++