Топологическая сортировка (реализация на Java)

Java   31 мая 2015  Автор статьи: admin 

Задан ориентированный граф, состоящий из N вершин и M дуг. Требуется найти топологическую сортировку (topological sort) вершин этого графа, то есть указать такой линейный порядок на его вершинах, что любая дуга ведет от меньшей вершины к большей в смысле этого порядка. В случае, если орграф не является ациклическим и такого порядка не существует, то вывести сообщение об этом.

Для решения данной задачи исходный орграф G удобно представлять в памяти ЭВМ списком смежности adj, храня для каждой вершины графа v список adj[v] смежных с ней вершин. Массив color служит для хранения цветов вершин. Белой вершине v соответствует значение 0 в ячейке color[v], color[v] = 0. Если вершина v в процессе обхода стала серой, то color[v] = 1, если стала черной, то color[v] = 2. Топологически упорядоченная перестановка номеров вершин орграфа хранится при помощи списка topSort.


//список смежности
private ArrayList adj[];
//массив для хранения цветов вершин
private int color[];
//топологически упорядоченная перестановка вершин графа
private ArrayList topSort;

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

В приведенной ниже реализации данные считываются и выводятся в консоль.

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

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

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

Если орграф не является ациклическим и содержит один или более циклов, то в первой строке выводится слово «Сyclic». Если орграф является ациклическим, то в строке выводится N чисел через пробел — топологическая сортировка вершин орграфа.

 


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 int color[];
//флаг, показывающий содержит орграф цикл или нет
private boolean cyclic = false;
//топологически упорядоченная перестановка вершин графа
ArrayList topSort;

private BufferedReader cin;
private PrintWriter cout;
private StringTokenizer tokenizer;

//топологическая сортировка вершин графа
private void topologicalSort(int v) {
//если вершина является черной, то не производим из нее вызов процедуры
if (color[v] == 2) {
return;
}
//выходим из процедуры, если уже нашли один из циклов
if (cyclic) {
return;
}
//если вершина является серой, то орграф содержит цикл
if (color[v] == 1) {
cyclic = true;
return;
}
color[v] = 1; //помечаем вершину как серую
//запускаем обход из всех вершин, смежных с вершиной v
for (int i = 0; i < adj[v].size(); ++i) { int w = adj[v].get(i); //вызов обхода от вершины w, смежной с вершиной v topologicalSort(w); if (cyclic) { return; } } color[v] = 2; //помечаем вершину как черную //добавляем посещенную вершину в топологический порядок topSort.add(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()); //считываем количество ребер графа //инициализируем список смежности графа размерности n adj = new ArrayList[n]; for (int i = 0; i < n; ++i) { adj[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); } //помечаем все вершины, как белые color = new int[n]; Arrays.fill(color, 0); cyclic = false; topSort = new ArrayList();
}

//процедура вывода данных в консоль
private void printData() throws IOException {
//если граф содержит цикл то выводим сообщение об этом
if (cyclic) {
cout.println("Cyclic");
//иначе выводим топологически упорядоченную перестановку его вершин
} else {
for (int v = 0; v < n; ++v) { cout.print((topSort.get(v) + 1) + " "); } cout.println(); } cin.close(); cout.close(); } private void run() throws IOException { readData(); //запускаем процедуру, которая топологически сортирует вершины графа for (int v = 0; v < n; ++v) { topologicalSort(v); } if (!cyclic) { for (int v = 0; v < n / 2; ++v) { int temp = topSort.get(v); topSort.set(v, topSort.get(n - v - 1)); topSort.set(n - v - 1, temp); } } printData(); } public static void main(String[] args) throws IOException { Solution solution = new Solution(); solution.run(); } }

 

Пример
Входные данные
9 9
1 4
1 5
2 5
4 5
4 7
6 3
7 9
8 7
8 9
Выходные данные
8 6 3 2 1 4 7 9 5

 

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

  • на Delphi

  • на Java

  • на C++