LeetCode 之 Course Schedule I（图-广搜）

古城微笑少年丶 2022-08-08 09:09 104阅读 0赞

【题目】

选课问题，共有N个待选课程，其中某些课程有学习次序，例如：学完编号1课程才能去学习编号0课程，且我们将它表示为[0,1]。现给出全部待选课程数目与课程间的学习次序，请根据次序要求与课程判断能否完成全部课程并给出选课次序。

【解析】

题目较之前有改动，阐释如下：

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
      	}

以及

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { }

是新老两个题目的 Title 两者的区别 在于 vector<pair<int, int>>和vector<vector<int>> ，分清二者并解决之是现如今的关键 ！这里是leetcode 对题目作了修缮，因此，现在需要找到新的解决方法！现在先对原来的老方法做出一定的学习！

**知识点1. 图结构**（树-只需要知道树的顶点，而图需要知道 顶点数目+顶点邻接表+当前顶点入度集合），邻接表是边集合，入度表示点的前驱集合。

>     成员
> 
>     顶点数目、顶点邻接表、当前顶点入度集合、当前顶点入度为0集合
> 
>     方法
> 
>     构造函数（初始化顶点数目+顶点邻接表+当前顶点入度集合）
> 
>     析构函数（析构 邻接表与入度集合 空间）
> 
>     边际添加函数（构建 邻接表）

**知识点2. 拓扑排序**

> **核心思想**：创建并维护一个当下入度为0的List（链表）；
> 
> **算法实现：**将入度为 0 的顶点弹出 --> 对非 0 入度顶点减度 --> 找到新一轮入度为 0 的顶点 ；不断迭代，直到结束； 返回是否排序完成，即能否完成全部课程。）
> 
>   
>

TopoSort 源码

/************************类声明************************/
    class Graph
    {
        int V;             // 顶点个数
        list<int> *adj;    // 邻接表，这里的邻接表也可称为 出度表
        queue<int> q;      // 维护一个入度为0的顶点的集合
        int* indegree;     // 记录每个顶点的入度
    public:
        Graph(int V);                   // 构造函数
        ~Graph();                       // 析构函数
        void addEdge(int v, int w);     // 添加边
        bool topological_sort();        // 拓扑排序
    };
    /************************类定义************************/
    Graph::Graph(int V)
    {
        this->V = V;
        adj = new list<int>[V];
        indegree = new int[V];  // 入度全部初始化为0
        for(int i=0; i<V; ++i)
            indegree[i] = 0;
    }
    Graph::~Graph()
    {
        delete [] adj;
        delete [] indegree;
    }
    void Graph::addEdge(int v, int w)
    {
        adj[v].push_back(w); 
        ++indegree[w];
    }
    bool Graph::topological_sort()
    {
        for(int i=0; i<V; ++i)
            if(indegree[i] == 0)
                q.push(i);         // 将所有入度为0的顶点入队
        int count = 0;             // 计数，记录当前已经输出的顶点数 
        while(!q.empty())
        {
            int v = q.front();      // 从队列中取出一个顶点
            q.pop();
            //cout << v << " ";      // 输出该顶点
            ++count;
            // 将所有v指向的顶点的入度减1，并将入度减为0的顶点入栈
            list<int>::iterator beg = adj[v].begin();
            for( ; beg!=adj[v].end(); ++beg)
                if(!(--indegree[*beg]))
                    q.push(*beg);   // 若入度为0，则入栈
        }
        if(count < V)
            return false;           // 没有输出全部顶点，有向图中有回路
        else
            return true;            // 拓扑排序成功
    }

采用TopoSort算法实现选课：

创建图对象 --> 添加边界 --> 拓扑排序
    class Solution {
    public:
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
            Graph g(numCourses);  // 创建图
            for(int i=0; i<prerequisites.size(); ++i)
                g.addEdge(prerequisites[i][1], prerequisites[i][0]);
            return g.topological_sort();
        }
    };
    
    简化源码：

【一】

class Solution {
    public:
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
            vector<vector<int>> graph(numCourses, vector<int>(0));
            vector<int> inDegree(numCourses, 0);
            for (auto u : prerequisites) { 
                graph[u[1]].push_back(u[0]);
                ++inDegree[u[0]];
            }
            queue<int> que;
            for (int i = 0; i < numCourses; ++i) {
                if (inDegree[i] == 0) que.push(i);
            }
            while (!que.empty()) {
                int u = que.front();
                que.pop();
                for (auto v : graph[u]) {
                    --inDegree[v];
                    if (inDegree[v] == 0) que.push(v);
                }
            }
            for (int i = 0; i < numCourses; ++i) {
                if (inDegree[i] != 0) return false;
            }
            return true;
        }
    };
    【二】
    class Solution {  
    public:  
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {  
            if(prerequisites.size()<=1)  
                return true;  
              
            unordered_map<int,vector<int>> table;  
            for(auto &i:prerequisites)  
            {  
                table[i[0]].push_back(i[1]);  
            }  
           vector<int> path;  
            while(!table.empty())  
            {  
                auto it=table.begin();  
                path.push_back(it->first);  
                if(HasLoop(table,it->first,path))  
                    return false;  
                path.pop_back();  
            }  
            return true;  
        }  
        //判断是否有环，有环的话返回真，否则返回假  
        bool HasLoop( unordered_map<int,vector<int>> &table,const int &begin,vector<int> &path)  
        {  
           if(table.count(begin)==0)  
             return false;  
           while(!table[begin].empty())  
           {  
               int temp=table[begin].back();  
               if(find(path.begin(),path.end(),temp)!=path.end())  
                    return true;  
                path.push_back(temp);  
               if(HasLoop(table,temp,path))  
                    return true;  
                path.pop_back();  
                table[begin].pop_back();  
           }  
           table.erase(begin);  
           return false;  
        }  
    };  
    
    【待完善】
    
     
      
       
        
         整理 auto 类型变量相关知识； 
         什么时候用 点 什么时候用  箭头 
         http://www.cnblogs.com/BeyondAnyTime/category/379485.html 
         http://blog.csdn.net/linxinyuluo/article/details/6847851 
         http://blog.csdn.net/linxinyuluo/article/details/6845947