я просматриваю разные алгоритмы, в том числе - есть красивая задачка про топологическую сортировку:
дан ориентированный граф, то есть, набор вершин, соединенных стрелочками. Можно ли так занумеровать вершины, чтобы любая стрелочка вела от числа с меньшим номером к числу с бОльшим номером?
Пример:
Понятно, что это должен быть граф без циклов.
И я легко нагуглил, что такой алгоритм поиска тополологической сортировки называется "алгоритмом Тарьяна"
А дальше начинается мистика.
Во многих местах алгоритм Тарьяна и даже задача, которую он решает, сформулированы совершенно иначе: "Алгоритм Тарьяна для поиска LCA оффлайн (ближайшего общего предка (least common ancestor, LCA))"
я понимаю, что есть, видимо, какой то красивый переход от одной формулировки задачи к другой, но не могу найти, что это за переход? И есть ли объяснение алгоритма Тарьяна именно для топологической сортировки?
В коменатриях мне подсказали, что, веротяно, у Тарьяна два совершенно разных "именных" и не связанных по смыслу друг с другом алгоритма. Так ли это?
Дополнение:
я нашел сравнительно понятную статью, (на которую мне указал и Станислав Володарский в комментариях)
Потом я переписал в VSC программу, на которую приведена ссылка вниуз статьи.
При этом я взял граф, приведенный в статье в "Пример работы алгоритма", и заменил буквы в названиях вершин на числа от 1 до 5. И ввел туда 8 рёбер.
Результат работы программы - парадоксальный: она выдала 0 1 3 5 4 2
. А теперь, внимание, вопрос: а что же это такое?
Программа:
#include <iostream>
#include <vector>
#include <conio.h>
using namespace std;
int n=5; // число вершин
vector<int> g[8]; // граф
bool used[8];
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());
}
int main(){
g[0] = {1, 2};
g[1] = {1, 3};
g[2] = {1, 4};
g[3] = {1, 5};
g[4] = {2, 4};
g[5] = {3, 4};
g[6] = {3, 5};
g[7] = {4, 5};
topological_sort();
for( size_t i=0; i<ans.size(); ++i )
cout << ans[i] << " ";
getch();
}
Картинка с результатом: