MAXimal | |
добавлено: 10 Jun 2008 19:24 Содержание [скрыть] Топологическая сортировкаДан ориентированный граф с вершинами и рёбрами. Требуется перенумеровать его вершины таким образом, чтобы каждое рёбро вело из вершины с меньшим номером в вершину с большим. Иными словами, требуется найти перестановку вершин (топологический порядок), соответствующую порядку, задаваемому всеми рёбрами графа. Топологическая сортировка может быть не единственной (например, если граф — пустой; или если есть три такие вершины , , , что из есть пути в и в , но ни из в , ни из в добраться нельзя). Топологической сортировки может не существовать вовсе — если граф содержит циклы (поскольку при этом возникает противоречие: есть путь и из одной вершины в другую, и наоборот). Распространённая задача на топологическую сортировку — следующая. Есть переменных, значения которых нам неизвестны. Известно лишь про некоторые пары переменных, что одна переменная меньше другой. Требуется проверить, не противоречивы ли эти неравенства, и если нет, выдать переменные в порядке их возрастания (если решений несколько — выдать любое). Легко заметить, что это в точности и есть задача о поиске топологической сортировки в графе из вершин. АлгоритмДля решения воспользуемся обходом в глубину. Предположим, что граф ацикличен, т.е. решение существует. Что делает обход в глубину? При запуске из какой-то вершины он пытается запуститься вдоль всех рёбер, исходящих из . Вдоль тех рёбер, концы которых уже были посещены ранее, он не проходит, а вдоль всех остальных — проходит и вызывает себя от их концов. Таким образом, к моменту выхода из вызова все вершины, достижимые из как непосредственно (по одному ребру), так и косвенно (по пути) — все такие вершины уже посещены обходом. Следовательно, если мы будем в момент выхода из добавлять нашу вершину в начало некоего списка, то в конце концов в этом списке получится топологическая сортировка. Эти объяснения можно представить и в несколько ином свете, с помощью понятия "времени выхода" обхода в глубину. Время выхода для каждой вершины — это момент времени, в который закончил работать вызов обхода в глубину от неё (времена выхода можно занумеровать от до ). Легко понять, что при обходе в глубину время выхода из какой-либо вершины всегда больше, чем время выхода из всех вершин, достижимых из неё (т.к. они были посещены либо до вызова , либо во время него). Таким образом, искомая топологическая сортировка — это сортировка в порядке убывания времён выхода. РеализацияПриведём реализацию, предполагающую, что граф ацикличен, т.е. искомая топологическая сортировка существует. При необходимости проверку графа на ацикличность легко вставить в обход в глубину, как описано в статье по обходу в глубину. int n; // число вершин vector<int> g[MAXN]; // граф bool used[MAXN]; vector<int> ans; void dfs (int v) { used[v] = true; for (size_t i=0; i<g[v].size(); ++i) { int to = g[v][i]; if (!used[to]) dfs (to); } ans.push_back (v); } void topological_sort() { for (int i=0; i<n; ++i) used[i] = false; ans.clear(); for (int i=0; i<n; ++i) if (!used[i]) dfs (i); reverse (ans.begin(), ans.end()); } Здесь константе следует задать значение, равное максимально возможному числу вершин в графе. Основная функция решения — это topological_sort, она инициализирует пометки обхода в глубину, запускает его, и ответ в итоге получается в векторе . Задачи в online judgesСписок задач, в которых требуется искать топологическую сортировку:
|