Представление списка смежности в топологической сортировке

Я видел следующую реализацию топологической сортировки с использованием DFS на Leetcode https://leetcode.com/problems/course-schedule/discuss/58509/18-22-lines-C++-BFSDFS-Solutions

Что меня смущает, так это представление ориентированного графа, которое используется для верхней сортировки. График создается следующим образом:

vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<unordered_set<int>> graph(numCourses);
    for (auto pre : prerequisites)
        graph[pre.second].insert(pre.first);
    return graph;
}

Меня смущает эта строка:

    graph[pre.second].insert(pre.first);

Предположительно граф представлен как список смежности; если да, то почему каждый узел представлен входящими ребрами, а не исходящими? Интересно, что если я переверну pre.second и pre.first вот так:

graph[pre.first].insert(pre.second);

Верхний сорт все еще работает. Однако, похоже, что в большинстве реализаций той же проблемы используется первый метод. Распространяется ли это на все ориентированные графы? В бакалавриате меня учили, что список смежности ориентированного графа должен содержать список исходящих узлов каждого узла. Является ли выбор входящего и исходящего узла произвольным для представления списка смежности?


c++ algorithm data-structures graph-theory topological-sort
person user3586940    schedule 04.03.2019    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Что касается конкретной проблемы, требующей только ответа true или false, не имеет значения, переворачиваете ли вы каждый край. Это потому, что граф можно топологически сортировать тогда и только тогда, когда он не имеет петель. Но если вам нужен порядок приема, это не сработает, как вы можете видеть по различным результатам [[0, 1]] и [[1, 0]].

Какой способ сохранить график, зависит от того, как вы решите проблему. В данном случае нам нужно знать степени каждого узла (курс), а также обновлять его каждый раз, когда мы удаляем узел из графа (пройдите курс), чтобы мы знали, можем ли мы удалить узел (мы можем сделайте это, когда степень равна 0). При обновлении мы минус 1 каждому узлу, на который направляет удаленный узел. Если применить этот метод (как и большинство других), станет ясно, как сохранить график.

person Yang    schedule 04.03.2019
comment
Решение действительно генерирует правильный топологический порядок, если вы перевернете вектор или используете структуру LIFO. - person user3586940; 05.03.2019