面试必备-拓扑排序(附leetcode207 course schedule解答)

1. 拓扑序

如果图中从V到W有一条有向路径,则V一定排在W之前。满足此条件的顶点序列就称为一个拓扑序。
获得一个拓扑序的过程就是拓扑排序。
AOV如果有合理的拓扑序,则必定是有向无环图。

每一次要输出的是没有前驱顶点的那个顶点。没有前驱顶点就是入度为0,也就是没有一个顶点指向他。在输出的同时,就是把这个顶点抹掉。



2. 算法流程

void TopSort(){
    for(图中的每个顶点V){
        // 如果顶点的入度为0,那么将这个节点存到队列中
        if(Indegree[V] == 0)
            Enqueue(V, Q);
    }
    while(!IsEmpty(Q)){
        V = Dequeue(Q);
        输出V,或者记录V的输出序号;cnt++;
        // 遍历V的每个邻接点,并对他们的入度减1,如果入度为0,同样存到队列中
        for(V的每个邻接点W)
            if(--Indegree[W] == 0)
                Enqueue(W, Q);
    }
    if(cnt != |V|)
        ERROR("图中有回路");
}

这个算法还可以检测图是不是有向无环图

关键路径问题

哪些组是一天都不能耽误的,绝对不能延误的(没有机动时间的组)



问题1:整个工期有多长?

问题2: 哪几个组有机动时间?

从保证整个工期是18天,反推回去,看前面的节点最晚开始的时间。
机动时间的计算方式是:当前节点的最晚完成时间-上一节点的最早完成时间-两个节点之间的权重。


3. Leetcode 207. Course Schedule

https://leetcode.com/problems/course-schedule/

https://www.youtube.com/watch?v=fskPWs3Nuhc

step 1:把输出翻译成图的形式

用一个map来表示图。键为输出节点,值为图对应输出节点。
用一个vector来表示入度。


step2:获得一个拓扑序

  • 把入度为0(没有先修课程要求的课程放到队列里),典型的bfs模板
  • 把队列里的最先的节点取出来,,并且将节点的邻域节点的入度都减一。


  • 如果邻域节点的入度减为0以后,那么这个节点就被push进队列。


  • 依次类推。
  • 最后遍历所有点的入度,如果存在入度不等于0(如果有环,那么入度为负数),那么说明有环,返回false
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 使用邻接链表的方式构造图
        vector<int> input_node;
        vector<vector<int>> graph(numCourses, input_node);
        vector<int> indegree(numCourses, 0);
        int in_, out_;
        for(int i=0; i<prerequisites.size(); ++i){
            in_ = prerequisites[i][1];
            out_ = prerequisites[i][0];
            indegree[out_] += 1;
            graph[in_].push_back(out_);
        }
        
        // 把入度为0的节点存到队列中
        queue<int> q;
        for(int i=0; i<numCourses; ++i){
            if(indegree[i] == 0)
                q.push(i);
        }
        // 当队列不为空的时候,执行循环,取出入度为0的节点,并将邻接节点的入度减1
        while(!q.empty()){
            int zero_indegree = q.front();
            q.pop();
            int n = graph[zero_indegree].size();
            for(int i=0; i<n; ++i){
                int idx = graph[zero_indegree][i];
                if(--indegree[idx] == 0)
                    q.push(idx);
            }
        }
        
        // 如果存在入度不为0的节点,那么直接返回false
        for(int i=0; i<numCourses; ++i){
            if(indegree[i] != 0)
                return false;
        }
        return true;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。