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

Java   12 июня 2015  Автор статьи: admin 
geekbrains.ru/

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

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


//список смежности орграфа
private ArrayList adj[];
//список смежности транспонированного орграфа
private ArrayList adjT[];
//массив для хранения информации о пройденных и не пройденных вершинах
private boolean used[];
//массив для хранения информации о пройденных и не пройденных вершинах
ArrayList 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 в топологическом порядке в конденсации заданного орграфа.

 


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 adj[];
//список смежности транспонированного орграфа
private ArrayList adjT[];
//массив для хранения информации о пройденных и не пройденных вершинах
private boolean used[];
//массив для хранения информации о пройденных и не пройденных вершинах
ArrayList 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();
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();
}
}

 

Пример

Рассмотрим работу алгоритма на графе 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++

geekbrains.ru/
geekbrains.ru/