2

я просматриваю разные алгоритмы, в том числе - есть красивая задачка про топологическую сортировку:

дан ориентированный граф, то есть, набор вершин, соединенных стрелочками. Можно ли так занумеровать вершины, чтобы любая стрелочка вела от числа с меньшим номером к числу с бОльшим номером?

Пример:

граф с нумерацией

Понятно, что это должен быть граф без циклов.

И я легко нагуглил, что такой алгоритм поиска тополологической сортировки называется "алгоритмом Тарьяна"

А дальше начинается мистика.

Во многих местах алгоритм Тарьяна и даже задача, которую он решает, сформулированы совершенно иначе: "Алгоритм Тарьяна для поиска 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();
    }

Картинка с результатом:

парадоксальный результат

топологическая сортировка

5
  • Первая ссылка в вашем вопросе - не топологическая сортировка (если быть точным). 25 мая 2022 в 19:05
  • Нашёл сортировку Тарьяна: ru.wikipedia.org/wiki/… 25 мая 2022 в 19:08
  • Видимо у Тарьяна два именных алгоритма. Почему нет? 25 мая 2022 в 19:08
  • @StanislavVolodarskiy - да, спасибо, я тоже уже нашел эту статью с понятным объяснением алгоритма
    – S.H.
    25 мая 2022 в 19:10
  • Интересно, что всегда встречал его как Таржана... 27 мая 2022 в 18:31

1 ответ 1

1

Вы что-то не то делаете, заполняя g - это не список рёбер, а списки смежности, т.е. g[i] содержит вектор с номерами вершин, в которые есть дуги из i-й вершины. Поменяйте два раза [8] на [5] и

g[0] = { 1, 2, 3};
g[1] = { 3 };
g[2] = { 3, 4 };
g[3] = { 4 };
g[4] = { };

Рeзультат:

0 2 1 3 4
3
  • Семен семеныч! Огромное спасибо! Это еще раз доказывает, как легко сделать сайт с "так себе" (я сильно смягчил выражения) контентом, и как тяжело - с понятным контентом. О том, что такое g[] -= на исходной странице нет ни слова. А я гадаю - почему рёбра задаются не парами чисел, а целыми vector<int>...
    – S.H.
    26 мая 2022 в 10:21
  • @S.H. В одной из статей того сайта по элементарным алг. на графах упоминается Мы считаем, что граф задан списками смежности, т.е. g[i] содержит список вершин, в которые есть рёбра из вершины i, но не в идущих по логике ранее описаниях dfs и bfs. Автор, видимо, привык подразумевать это, и не брал в голову, что в отдельно взятой статье надо бы пояснить. В общем-то, по смыслу использования понятно, что это списки смежности, если есть некий опыт общения с графами.
    – MBo
    26 мая 2022 в 12:49
  • Согласен, когда пару недель занимаешься графами - то как то такое у тебя в голове закрепляется, когда же после рабочего дня пытаешься за пару часов въехать в тему - ну, 50 на 50, что догадаешься...
    – S.H.
    26 мая 2022 в 13:39

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.