Cybern8.com » Топологическая сортировка (реализация на С++)

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

C++

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

Статья
Комментарии (0)

Задан ориентированный граф, состоящий из $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$ .

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

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

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

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

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

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

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

#include #include


using namespace std;
int n; //количество вершин в орграфе

int m; //количествое дуг в орграфе

vector *adj; //список смежности
//массив для хранения цветов вершин

vector color;

//флаг, показывающий содержит орграф цикл или нет

bool cyclic = false;

//топологически упорядоченная перестановка вершин графа

vector topSort;
//процедура обхода в глубину

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) { //запускаем обход из всех вершин, смежных с вершиной v
        int w = adj[v][i];
        //вызов обхода от вершины w, смежной с вершиной v
        topologicalSort(w); 
        if (cyclic) {
            return;
        }
    }
    color[v] = 2; //помечаем вершину как черную
	//добавляем посещенную вершину в топологический порядок
	topSort.push_back(v);
}   

//процедура считывания данных с консоли
void readData() {
    scanf("%d %d", &n, &m); //считываем количество вершин и количество ребер графа
	adj = new vector[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); } //процедура вывода данных в консоль void printData() { if (cyclic) { printf("Cyclic\n"); } else { for (int v = 0; v < n; ++v) { printf("%d ", topSort[v] + 1); } printf("\n"); } //освобождаем память for (int i = 0; i < n; ++i) { adj[i].clear(); } delete[] adj; color.clear(); topSort.clear(); } int main() { readData(); for (int v = 0; v < n; ++v) { topologicalSort(v); } if (!cyclic) { for (int v = 0; v < n / 2; ++v) { swap(topSort[v], topSort[n - v - 1]); } } printData(); return 0; }

Пример

Входные данные
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++

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

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

на Delphi

на Java

на C++