Leetcode 207. 课程表-图-深度优先搜索

Leetcode 207. 课程表-图-深度优先搜索

解题思路:

  • 如题目所示,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。实际上可以想象为有一个值为1的结点指向值为0的结点,而且每一个可以指向的结点数量并不固定,所以就是个有向图,而要想判断是否能够完成,实际上对于图来说如果存在环那么就意味着存在两个结点互相指向(互相需要),所以如果存在环那么一定无法学完所有课程
  • 注意:
    1.如何将题目所给参数转化为抽象的图结构
    2.如何进行深度优先搜索
    3.如何判断是否存在环结构
class Solution {
// 本题思路是将题目转化未有向图结构,利用深度优先搜索来判断是否存在环,如果图中存在环那么就不可能完成所有课程的学习
private:
    // 存储有向图
    vector<vector<int>>edges;
    //存储结点状态0=未搜素,1=正在搜索,2=搜索完成
    vector<int>visited;
    // 假设不存在环
    bool valid = true;
public:
    void dfs(int u){
        visited[u]=1;
        for(int v:edges[u]){
            if(visited[v]==0){
                dfs(v);
                if(!valid)return;
            }
            // 在进行深度优先搜索时,搜索到了一个已经正在搜索的,说明形成了环
            else if(visited[v]==1){
                valid = false;
                return;
            }
        }
        // 搜索结束后要将该结点的标志进行修改
        visited[u] = 2;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        // 转换成有向图存储
        for(auto temp:prerequisites){
            edges[temp[1]].push_back(temp[0]);
        }
        for(int i = 0;i<numCourses && valid;++i){
            if(visited[i]==0){
                dfs(i);
            }
        }
        return valid;
    }
};
上一篇:422,剑指 Offer-使用DFS和BFS解机器人的运动范围


下一篇:深度和广度优先搜索算法