引入

离散教材上讲过关键路径。其中,在求最长路径时,第一步是对节点进行“重新标号”。经过查阅,发现这个步骤其实叫做“拓扑排序”。很容易知道,如果一个图可以拓扑排序,那个它是有向无环图(DAG, Directed Acyclic Graph),从而它可能是一个能反映事件先后依赖关系的PT图(Potentialtask Graph)。

问题

(1) LeetCode #207

“能完成学习”说明给的图是DAG。用拓扑排序判断给定图是否是DAG图即可。即如果还有节点没有标号时,图中就找不到入度为0的点了,那么就不是DAG。反之,能顺利给所有点标号,就是DAG。

(2) LeetCode #210

本题其实就是在1的基础上,把拓扑排序的结果输出出来。

(3) LeetCode #1203

本题要求每个小组的工作排在一起。其实,这是一个双重(嵌套)拓扑排序的结构。可以先将每个组的工作“打包”构建整个小组之间的PT图(先后关系)进行拓扑排序,然后对每个组内的工作再进行拓扑排序。

实现

(1)

本题有两点实现上的技巧。

一开始实现的时候比较愚笨地把给的边列表转换成了邻接矩阵。但其实本题用邻接表(adjacency list)在空间和时间上都更优。因为,在删除一个点,需要知道它的直接后继时,用邻接表可以直接遍历这个点的后继列表,而邻接矩阵需要遍历所有的点并用if判断。同时,为了避免不断地盲目扫描全部节点来获取入度为0的点,应该借助一个队列。一开始,把所有入度为0的点加入队列。由于每个点的入度变化是每次删除一个点时可能减1,也就是新产生的入度为0的点一定是删除某个点时它的入度从1变成0,因此一边删除点,就可以一边把新的入度为0的点加入队列。队列空了之后,判断是否删除了所有点即可。

LeetCode的输入数据往往给的是边列表。从此题可以看出,边列表有时应转换成邻接矩阵,有时应转换成邻接表。(说不定有时也可以直接使用。)

class Solution
{
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        vector<int> pre_num(numCourses, 0);
        vector< vector<int> > adjacency(numCourses);
        for (auto iter : prerequisites)
        {
            // iter[1] -> iter[0]
            pre_num[ iter[0] ]++;
            adjacency[ iter[1] ].push_back(iter[0]);
        }
        queue<int> q;
        for (int i = 0; i < numCourses; i++)
        {
            if (pre_num[i] == 0)
                q.push(i);
        }
        int n = numCourses;
        while (!q.empty())
        {
            int node_to_del = q.front();
            q.pop();
            n--;
            for (auto iter : adjacency[node_to_del])
            {
                pre_num[iter]--;
                if (pre_num[iter] == 0)
                    q.push(iter);
            }
        }
        return n == 0;
    }
};

(2)

对1略加改造即可。

class Solution
{
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)
    {
        vector<int> order;
        vector< vector<int> > adjacency(numCourses);
        vector<int> pre_num(numCourses, 0);
        for (auto iter : prerequisites)
        {
            // iter[1] -> iter[0]
            adjacency[ iter[1] ].push_back(iter[0]);
            pre_num[ iter[0] ]++;
        }
        queue<int> q;
        for (int i = 0; i < numCourses; i++)
        {
            if (pre_num[i] == 0)
                q.push(i);
        }
        while (!q.empty())
        {
            int node_to_del = -1;
            node_to_del = q.front();
            q.pop();
            order.push_back(node_to_del);
            for (auto iter : adjacency[node_to_del])
            {
                // node_to_del -> iter
                pre_num[iter]--;
                if (pre_num[iter] == 0)
                    q.push(iter);
            }
        }
        if (order.size() == numCourses)
            return order;
        else
            return vector<int>(0);
    }
};
Last modification:June 25th, 2020 at 09:04 pm
如果觉得我的文章对你有用,请随意赞赏