拓扑排序之课程表问题 bfs, dfs 双解

        拓扑排序指的是有向无环图（DAG），「拓扑排序」是专门应用于有向图的算法。

        下面就是一个拓扑结构；

拓扑序就是，图中任意一对顶点u和v，若边∈E(G)，则u在线性序列中出现在v之前

我们可以发现拓扑序不是唯一的；

接下来，我们需要知道一个概念——度：

对于有向图的某个结点来说，我们把指向它的边的数量叫做入度；

把从它发出的边的数量称为出度

拓扑序的问题有两个条件：不存在环，有向。

 

题目：

        这道题用 BFS 和 DFS 都可以完成，BFS 的写法很经典，BFS 的写法就叫「拓扑排序」，这里还用到了贪心算法的思想，贪的点是：当前让入度为 0 的那些结点入队。

BFS的代码思路：

BFS表示广度优先遍历，即每次把节点的邻居都访问完了，再继续访问下一层的节点。使用了队列存储节点的顺序。

1）首先遍历得到每个节点的入度数，以及有向图的字典，即每个节点课程结束后，哪些课程可以继续执行的字典映射。比如，节点1,2，依赖节点0的执行，所以在字典中{ 0: [1,2] }

2）然后建立一个队列，队列具有先进先出的特点，先把入度为0的点，加进队列中。表示这些节点的课可以先修完，他们不依赖其它课程。

3）最后，建立队列的循环，每次出一个节点，知道所有入度为0的节点都出来了，队列为空退出循环，此时队列一次出来的节点顺序就是所求答案。

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        if len(prerequisites)==0:
            return list(range(numCourses))
 
        in_degree=[0]*numCourses
        adj=[set() for _ in range(numCourses)]
        for s, f in prerequisites:
            in_degree[s]+=1
            adj[f].add(s)
        queue=[]
        res=[]
        for i in range(numCourses):
            if in_degree[i]==0:
                queue.append(i)
        while len(queue)>0:
            cur=queue.pop(0)
            res.append(cur)
            for succe in adj[cur]:
                in_degree[succe]-=1
                if in_degree[succe]==0:
                    queue.append(succe)
        if len(res)!=numCourses:
            return []
        return res

DFS的代码思路：

        DFS表示深度优先遍历。指遍历节点的一条路径到底，由图的低部向上回溯，中间的节点通过栈的结构存储，先进后出即为所求答案。

1）遍历每个节点，同样先建立每个节点的依赖关系字典结构。

2）建立有n个节点的visited数组，记录每个节点是否在访问，访问中，访问结束。以及是否有环的标记hasCycle。有环的情况下，无法输出拓扑排序。

3）写dfs函数，传入当前的节点。把该节点的visited标记为1，表示正在访问。

如果依赖字典中不存在该节点，则可以直接标记visited=2，表示已经访问过，stack 压入该节点。

否则遍历每一个依赖该节点的邻居节点，

• 如果visited[node]=0，表示未访问过，递归将该节点进入dfs函数，结束后判断是否hasCycle=True，如果是则遇到环，退出函数。
• 如果visited[node]=1表示正在访问中又进入了，则存在环hasCycle=True, 退出函数。

最后，将visited[node]=2，表示进入dfs的这个节点已经访问过了，避免重复访问，并把该节点压入stack栈。

4） 依次遍历每个节点，如果visited[node]==0则进入dfs函数。最后将stack依次弹出，即为所求答案。栈的弹出对于list来说，就是把每个数反着输出。

如果hasCycle=True,则有环，没有拓扑顺序。

class Solution:
    def findOrder(self, numCourses: int, prerequisites):
        def dfs(s):
            nonlocal hasCycle
            visited[s]=1
            if s in graph:
                for v in graph[s]:
                    if visited[v]==0:
                        dfs(v)
                        if hasCycle:
                            return
                    elif visited[v]==1:
                        hasCycle=True
                        return
            visited[s]=2
            stack.append(s)
            return
 
        visited=[0]*numCourses
        hasCycle=False
        graph={}
        stack=[]
        for s,f in prerequisites:
            if f not in graph:
                graph[f]=[s]
            else:
                graph[f].append(s)
        for i in range(numCourses):
            if visited[i]==0 and not hasCycle:
                dfs(i)
        return stack[::-1] if not hasCycle else []

复习一下C++的BFS实现：

class Solution {
private:
    vector <int> in_degree;
    vector <int> result;
    vector int>> edges;
 
public:
    vector<int> findOrder(int numCourses, vectorint>>& prerequisites) {
 
        edges.resize(numCourses);
        in_degree.resize(numCourses);
        for (const auto& info: prerequisites){
            edges[info[1]].push_back(info[0]);
            ++in_degree[info[0]];
        }
 
        queue<int> q;
        for(int i=0;i
            if (in_degree[i]==0){
                q.push(i);
            }
        }
 
        while(!q.empty()){
            int u=q.front();
            q.pop();
            result.push_back(u);
            for(int v:edges[u]){
                --in_degree[v];
                if (in_degree[v]==0){
                    q.push(v);
                }
            }
        }
 
        if (result.size() !=numCourses){
            return {};
        }
        return result;
 
    }
};