拓扑排序

思路：判定所给图是否为有向无环图。(即是否能够进行拓扑排序)

DFS、BFS实现

广度优先遍历

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        if(prerequisites.empty()) return true;
        // 采用邻接表法
        vector<vector<int>>v(numCourses,vector<int>());
        // 保存各结点入度
        vector<int>inDegree(numCourses,0);
        int cnt = 0;

        // BFS 
        queue<int>q;
        for(auto v1 : prerequisites)
        {
            inDegree[v1[0]]++;
            v[v1[1]].push_back(v1[0]);
        }
       // 度为0的结点入队
        for(int i=0;i<numCourses;++i)
        {
            if(inDegree[i]==0)
                q.push(i);
        }
        while(!q.empty())
        {
            auto node = q.front();
            q.pop();
            cnt ++;
            // 一个结点出队后，将它指向的结点的入度-1
            for(int i=0;i<v[node].size();++i)
            {
                if(--inDegree[v[node][i]]==0)
                    q.push(v[node][i]);
            }
        }
// 出队结点数是否等于给定结点数
        return cnt  == numCourses;
    }
};

深度优先遍历

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        if(prerequisites.empty()) return true;
        // 采用邻接表法
        vector<vector<int>>v(numCourses,vector<int>());
        for(auto v1 : prerequisites)
        {
            v[v1[1]].push_back(v1[0]);
        }

        // DFS 记忆化搜索
        // flags标志位来记录结点状态：0 未访问;  
        // 1 由本次发起dfs的结点出发访问到,说明有环; 
        // -1 由非本次发起dfs的结点访问过 
        vector<int>flags(numCourses,0);

        for(int i=0;i<numCourses;++i)
            if(!dfs(v,flags,i))
                return false;
        return true;
    }
    bool dfs(vector<vector<int>>& v,vector<int>& flags,int k)
    {
        if(flags[k]==1) return false;
        if(flags[k]==-1) return true;

        flags[k] = 1;
        for(int i=0;i<v[k].size();++i)
        {
            if(!dfs(v,flags,v[k][i])) return false;
        }
        flags[k] = -1;
        return true;
    }
};