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

C++   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 служит для хранения предков вершин в дереве обхода орграфа.

1
2
3
4
5
vector<int> *adj; //список смежности
//массив для хранения цветов вершин
vector<int> color;
//массив предков, необходимых для восстановления цикла, в случае его наличия в графе
vector<int> pred;

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

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

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

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

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

 

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
#include <iostream>
#include <vector>

using namespace std;

int n; //количество вершин в орграфе
int m; //количествое дуг в орграфе
vector<int> *adj; //список смежности

//массив для хранения цветов вершин
vector<int> color;
//массив предков, необходимых для восстановления цикла, в случае его наличия в графе
vector<int> pred;  
//флаг, показывающий содержит орграф цикл или нет
bool cyclic = false;
vector<int> cycle; //цикл

//процедура обхода в глубину
void dfsCycle(int v) {
    //если вершина является черной, то не производим из нее вызов процедуры
    if (color[v] == 2) {
        return;
    }
    //выходим из процедуры, если уже нашли один из циклов
    if (cyclic) {
        return;
    }
    //если вершина является серой, то орграф содержит цикл
    if (color[v] == 1) {
        cyclic = true;
        //сохраняем цикл
        cycle.push_back(v);
        for (int ver = pred[v]; ver != v; ver = pred[ver]) {
            cycle.push_back(ver);
        }
        cycle.push_back(v);
        for (int i = 0; i < cycle.size() / 2; ++i) {
            swap(cycle[i], cycle[cycle.size() - 1 - i]);
        }
        return;
    }
    color[v] = 1; //помечаем вершину как серую
    //запускаем обход из всех вершин, смежных с вершиной v
    for (int i = 0; i < adj[v].size(); ++i) { //запускаем обход из всех вершин, смежных с вершиной v
        int w = adj[v][i];
        //вершина v - это предок вершины w при обходе
        pred[w] = v;
        //вызов обхода от вершины w, смежной с вершиной v
        dfsCycle(w);
        if (cyclic) {
            return;
        }
    }
    color[v] = 2; //помечаем вершину как черную
}  

//процедура считывания данных с консоли
void readData() {
    scanf("%d %d", &n, &m); //считываем количество вершин и количество ребер графа
    adj = new vector<int>[n];

    //считываем граф, заданный списком ребер
    for (int i = 0; i < m; ++i) {
        int v, w;
        scanf("%d %d", &v, &w);
        v--;
        w--;
        adj[v].push_back(w);
    }
    cyclic = false;
    color.assign(n, false);
    pred.assign(n, false);
}

//процедура вывода данных в консоль
void printData() {
    if (cyclic) {
        printf("Cyclic\n");
        printf("%d\n", cycle.size() - 1);
        for (int i = 0; i < cycle.size(); ++i) {
            printf("%d ", (cycle[i] + 1));
        }
        printf("\n");
    } else {
        printf("Acyclic\n");
    }
       
    //освобождаем память
    for (int i = 0; i < n; ++i) {
        adj[i].clear();
    }
    delete[] adj;
    color.clear();
    pred.clear();
    cycle.clear();
}

int main()
{
    readData();
    for (int v = 0; v < n; ++v) {
        dfsCycle(v);
    }
    printData();
    return 0;
}

 

Пример 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++