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

C++   12 Июнь 2015  Автор статьи: admin 

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

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

1
2
3
4
5
6
7
8
9
vector<int> *adj; //список смежности орграфа
vector<int> *adjT; //список смежности транспонированного орграфа
//массив для хранения информации о пройденных и не пройденных вершинах
vector<bool> used;
//топологически упорядоченная перестановка вершин графа
vector<int> topSort;
//массив для обозначения компонент сильной связности орграфа
vector<int> component;
int componentCount; //количество компонент связности в орграфе

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

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

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

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

На первой строке выходного файла выводится число L — количество компонент сильной связности заданного орграфа. На следующей строке выводится N чисел из диапазона от 1 до L — номера компонент сильной связности, которым принадлежат соответствующие вершины. Компоненты сильной связности нумеруются от 1 до L в топологическом порядке в конденсации заданного орграфа.

 

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

using namespace std;

int n; //количество вершин в орграфе
int m; //количество дуг в орграфе
vector<int> *adj; //список смежности орграфа
vector<int> *adjT; //список смежности транспонированного орграфа
//массив для хранения информации о пройденных и не пройденных вершинах
vector<bool> used;
//топологически упорядоченная перестановка вершин графа
vector<int> topSort;
//массив для обозначения компонент сильной связности орграфа
vector<int> component;
int componentCount; //количество компонент связности в орграфе

//процедура обхода в глубину
void dfs(int v) {
    //если вершина является пройденной, то не производим из нее вызов процедуры
    if (used[v]) {
        return;
    }
    used[v] = true; //помечаем вершину как пройденную
    //запускаем обход из всех вершин, смежных с вершиной v
    for (int i = 0; i < adj[v].size(); ++i) { //запускаем обход из всех вершин, смежных с вершиной v
        int w = adj[v][i];
        //вызов обхода от вершины w, смежной с вершиной v
        dfs(w);
    }
    //добавляем посещенную вершину в топологический порядок
    topSort.push_back(v);
}  

//процедура я компонент сильной связности орграфа
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][i];
        ccs(w, componentID); //вызов обхода в глубину от вершины w, смежной с вершиной v в транспонированном графе
    }
}

//процедура считывания данных с консоли
void readData() {
    scanf("%d %d", &n, &m); //считываем количество вершин и количество ребер графа
    adj = new vector<int>[n];
    adjT = 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);
        //добавляем обратную дугу в транспонированный граф
        adjT[w].push_back(v);
    }
   
    //помечаем все вершины, как непосещенные
    used.resize(n, false);

    component.assign(n, 0);
}

//процедура вывода данных в консоль
void printData() {
    printf("%d\n", componentCount);
    for (int v = 0; v < n; ++v) {
        printf("%d ", component[v] + 1);
    }
    printf("\n");
       
    //освобождаем память
    for (int i = 0; i < n; ++i) {
        adj[i].clear();
    }
    delete[] adj;

    for (int i = 0; i < n; ++i) {
        adjT[i].clear();
    }
    delete[] adjT;

    used.clear();
    topSort.clear();
    component.clear();
}

void run() {
    readData();
    //запускаем обход в глубину для расчета времени выхода каждой вершины
    for (int v = 0; v < n; ++v) {
        dfs(v);
    }
       
    used.assign(n, false);
    int componentID = 0;
    for (int i = topSort.size() - 1; i >= 0; --i) {
        int v = topSort[i];
        if (!used[v]) {
            ccs(v, componentID);
            componentID++;
        }
    }
    componentCount = componentID;
    printData();
}

int main()
{
    run();
    return 0;
}

 

Пример

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