Топологическая сортировка (реализация на 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.

1
2
3
4
5
6
//список смежности
private ArrayList<Integer> adj[];
//массив для хранения цветов вершин
private int color[];
//топологически упорядоченная перестановка вершин графа
private ArrayList<Integer> topSort;

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

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

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

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

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

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

 

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
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 int color[];
    //флаг, показывающий содержит орграф цикл или нет
    private boolean cyclic = false;
    //топологически упорядоченная перестановка вершин графа
    ArrayList<Integer> 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<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);
        }
       
        //помечаем все вершины, как белые
        color = new int[n];
        Arrays.fill(color, 0);
       
        cyclic = false;
        topSort = new ArrayList<Integer>();
    }
   
    //процедура вывода данных в консоль
    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++