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

Question

Я видел следующую реализацию топологической сортировки с использованием 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);

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

Answer 1

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

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