BFS

994.腐烂的橘子

腐烂橘子的影响范围是周围一圈的橘子，这就是典型的BFS,类似于拓扑排序，每一轮bfs都记录一下

c++

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int dx[]={0,0,1,-1},dy[]={-1,1,0,0};//方向数组
        int m=grid.size(),n=grid[0].size();
        int res=0;
        queue<pair<int,int>> q;
        //1、初始化队列：添加烂橘子
        for(int i=0;i<m;++i)for(int j=0;j<n;++j)if(grid[i][j]==2)q.push({i,j});
       //2、进行bfs：将每层橘子中四个方向的好橘子感染成烂橘子，并添加到队列中
        while(!q.empty()){
            int span=q.size();
            for(int i=0;i<span;++i){
                pair<int,int> p=q.front();q.pop();
                for(int j=0;j<4;++j){//将每个烂橘子的4个方向的好橘子感染成烂橘子
                    int x=p.first+dx[j],y=p.second+dy[j];
                    if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1){
                        grid[x][y]=2;
                        q.push({x,y});
                    }
                }
            }
            if(!q.empty())res++;//感染完一圈的橘子，res+1
        }
        for(int i=0;i<m;++i)for(int j=0;j<n;++j)if(grid[i][j]==1)return -1;
        return res;
    }
};

207.课程表

这道题等价于判断图里有没有环，两种方法一个是拓扑排序，一个是DFS

拓扑排序

c++

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
      vector<int> degree(numCourses, 0);				//   map<int,int>degree;for(int i=0;i<numCourses;i++)degree[i]=0;
	  map<int,vector<int>>cur;	
        queue<int>q;
        for(int i=0;i<prerequisites.size();i++){
            cur[prerequisites[i][1]].push_back(prerequisites[i][0]);
            degree[prerequisites[i][0]]++;
        }
        for(int i=0;i<degree.size();i++) //不是cur.size()
        {
            if(degree[i]==0)
                q.push(i);
        }
        int ans=0;
        while(!q.empty())
        {
            int node=q.front();
            q.pop();
            ans++;
            for(int i=0;i<cur[node].size();i++)
            {
                degree[cur[node][i]]--;
                if(degree[cur[node][i]]==0)
                    q.push(cur[node][i]);
            }
        }
        if(ans==numCourses)return true;
        else return false;
    }
};

在这里我犯了一个错误，找了半天…啊我的时间都去哪了…
对于入度容器我开始设计是C++ map<int,vector<int>>cur这样没有考虑度为0的节点，首先默认节点入度都为0，然后根据图来更新入度，这种情况可以就地改进见注释，或者直接用vector初始化