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Список задач, в которых требуется искать топологическую сортировку:
|