Adjacency List Representation in Topological Sort

Question

I saw the following implementation of topological sort using DFS on Leetcode https://leetcode.com/problems/course-schedule/discuss/58509/18-22-lines-C++-BFSDFS-Solutions

Now the part of this that is confusing me is the representation of the directed graph which is used for the top sort. The graph is created as follows:

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;
}

What is confusing me is this line:

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

Presumably the graph is being represented as an adjacency list; if so why is each node being represented by the incoming edges and not the outgoing edges? Interestingly, if I flip pre.second and pre.first like this:

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

The top sort still works. However, it seems most implementations of the same problem use the former method. Does this generalize to all directed graphs? I was taught in my undergraduate degree that a directed graph's adjacency list should contain a list of each nodes outgoing nodes. Is the choice of incoming vs outgoing node arbitrary for the representation of the adjacency list?

Yang Yang · Accepted Answer · 2019-03-04T07:01:33

To the specific problem which only requires answering true or false, it doesn't matter if you flip every edge. That's because a graph is topological sortable if and only if it has no loops. But if you want an order of taking, it doesn't work as you can see in the different results of [[0, 1]] and [[1, 0]].

Which way to save the graph depends on how you solve the problem. In this given case, we need to know the indegrees of every node (course) and also to update it every time we delete a node from the graph (take the course), so that we know if we can delete a node (we can do it when the indegree is 0). When updating, we minus 1 to each node that the deleted node direct to. If you apply this method (as most do), it's clear how you should save the graph

Adjacency List Representation in Topological Sort

1 Answers