Поиск компонент сильной связности в орграфе (реализация на Java)
Задан ориентированный граф, состоящий из вершин и
дуг. Исходный орграф задается списком дуг. Требуется выделить в орграфе компоненты сильной связности.
Для решения данной задачи исходный орграф удобно представлять в памяти ЭВМ списком смежности
, храня для каждой вершины графа
список
смежных с ней вершин. Транспонированный орграф
также представляется в памяти ЭВМ списком смежности. Булевский массив
служит для отметки о том, стала вершина
посещенной в процессе обходов орграфа или еще нет. Топологически упорядоченная перестановка номеров вершин орграфа хранится при помощи списка
. Для принадлежности вершины к той или иной компоненте связности используется массив
. Количество компонент связности в орграфе хранится в переменной
.
//список смежности орграфа
private ArrayList
//список смежности транспонированного орграфа
private ArrayList
//массив для хранения информации о пройденных и не пройденных вершинах
private boolean used[];
//массив для хранения информации о пройденных и не пройденных вершинах
ArrayList
//массив для обозначения компонент сильной связности орграфа
private int[] component;
//количество компонент связности в орграфе
int componentCount;
В качестве списка смежности для представления орграфа и транспонированного орграфа на языке Java удобно использовать массив, каждый элемент которого является структурой данных .
В приведенной ниже реализации данные считываются и выводятся в консоль.
В первой строке входного файла задано два целых числа: – количество вершин в орграфе и
– количество дуг орграфа соответственно. Каждая из следующих
строк содержит описание дуги орграфа – два целых числа из диапазона от
до
, номер начала и конца дуги соответственно.
На первой строке выходного файла выводится число L — количество компонент сильной связности заданного орграфа. На следующей строке выводится N чисел из диапазона от 1 до L — номера компонент сильной связности, которым принадлежат соответствующие вершины. Компоненты сильной связности нумеруются от 1 до L в топологическом порядке в конденсации заданного орграфа.
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
//список смежности транспонированного орграфа
private ArrayList
//массив для хранения информации о пройденных и не пройденных вершинах
private boolean used[];
//массив для хранения информации о пройденных и не пройденных вершинах
ArrayList
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
adjT[i] = new ArrayList
}
//считываем граф, заданный списком дуг
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
}
//процедура вывода данных в консоль
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();
}
}
Рассмотрим работу алгоритма на графе , изображенном на рисунке.
В орграфе существует четыре компоненты сильной связности.
Соответственно, в ациклическом орграфе, который получится, если стянуть каждую сильно связную компоненту в точку, будет тоже четыре вершины. Такой ациклический орграф является конденсацией исходного орграфа.
Входные данные |
---|
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 |