Топологическая сортировка (реализация на С++)
Задан ориентированный граф, состоящий из вершин и
дуг. Требуется найти топологическую сортировку (topological sort) вершин этого графа, то есть указать такой линейный порядок на его вершинах, что любая дуга ведет от меньшей вершины к большей в смысле этого порядка. В случае, если орграф не является ациклическим и такого порядка не существует, то вывести сообщение об этом.
Для решения данной задачи исходный орграф удобно представлять в памяти ЭВМ списком смежности
, храня для каждой вершины графа
список
смежных с ней вершин. Массив
служит для хранения цветов вершин. Белой вершине
соответствует значение
в ячейке
,
. Если вершина
в процессе обхода стала серой, то
, если стала черной, то
. Топологически упорядоченная перестановка номеров вершин орграфа хранится при помощи списка
.
vector
//массив для хранения цветов вершин
vector
//топологически упорядоченная перестановка вершин графа
vector
В качестве списка смежности для представления графа на языке С++ удобно использовать динамический массив, каждый элемент которого является структурой данных .
В приведенной ниже реализации данные считываются и выводятся в консоль.
В первой строке входного файла задано два целых числа: – количество вершин в орграфе и
– количество дуг орграфа соответственно. Каждая из следующих
строк содержит описание дуги орграфа – два целых числа из диапазона от
до
, номер начала и конца дуги соответственно.
Если орграф не является ациклическим и содержит один или более циклов, то в первой строке выводится слово «Сyclic». Если орграф является ациклическим, то в строке выводится чисел через пробел — топологическая сортировка вершин орграфа.
#include
#include
using namespace std;
int n; //количество вершин в орграфе
int m; //количествое дуг в орграфе
vector
//массив для хранения цветов вершин
vector
//флаг, показывающий содержит орграф цикл или нет
bool cyclic = false;
//топологически упорядоченная перестановка вершин графа
vector
//процедура обхода в глубину
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
//считываем граф, заданный списком ребер
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 |