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

Java   28 марта 2015  Автор статьи:  

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

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


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

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

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

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

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

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

 


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

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

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

//процедура вывода данных в консоль
private void printData() throws IOException {
if (cyclic) {
cout.println("Cyclic");
cout.println(cycle.size() - 1);
for (int i = 0; i < cycle.size(); ++i) { cout.print((cycle.get(i) + 1) + " "); } cout.println(); } else { cout.println("Acyclic"); } cin.close(); cout.close(); } private void run() throws IOException { readData(); for (int v = 0; v < n; ++v) { dfsCycle(v); } printData(); } public static void main(String[] args) throws IOException { Solution solution = new Solution(); solution.run(); } }

 

Пример 1

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

демонстрация обхода в глубину

Орграф G_1 содержит цикл 1 \rightarrow 2 \rightarrow 3 \rightarrow 1. Стадии окрашивания вершин и посещения дуг орграфа G_1 изображены на схемах (a-г). После работы алгоритма на консоль будет выведена резолюция "Сусlic" и найденный в орграфе цикл.

Входные данные
4 4
1 2
2 3
3 1
3 4
Выходные данные
Cyclic
3
1 2 3 1

 

 

Пример 2

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

демонстрация обхода в глубину

Орграф G_2 является ациклическим. Стадии окрашивания вершин и посещения дуг орграфа G_2 изображены на схемах (a-и). После работы алгоритма на консоль будет выведена резолюция "Aсусlic".

Входные данные
4 4
1 2
2 3
3 4
1 4
Выходные данные
Acyclic

 

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

  • на Delphi

  • на Java

  • на C++