
class Solution {
public:
void bianli(vector<vector<int>>& isConnected,unordered_set<int>&hashset,int i){
    hashset.insert(i);
    for(int j=0;j<isConnected.size();j++){
       if(isConnected[i][j]!=0&&hashset.count(j)==0) {
           bianli(isConnected,hashset,j);
       }
    }
    
}
    int findCircleNum(vector<vector<int>>& isConnected) {
        int result=0;
        int len=isConnected.size();
        unordered_set<int>hashset;
        for(int i=0;i<len;i++){
            if(hashset.count(i)!=0){continue;}
            hashset.insert(i);
            result++;
            for(int j=0;j<len;j++){
                if(i==j){continue;}
                if(hashset.count(j)==0&&isConnected[i][j]!=0){
                    bianli(isConnected,hashset,j);
                    //cout<<hashset.count(j)<<endl;
                }
            }
        }
        return result;
    }
};

一条路走到黑

一个一个城市的处理，如果该城市没被处理过，看看哪个跟他有关系且没被处理过，逮住一个就往死里遍历，直到深度遍历的城市的邻居都是被处理过了的就返回。然后再返回去处理其余的。

宽度遍历：


class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int len=isConnected.size();
        int result=0;
        queue<int>q;
        vector<int>remember(len);
        for(int i=0;i<len;i++){
            if(remember[i]==0)
            {
                q.push(i);remember[i]=1;
                while(!q.empty()){
                    int xi=q.front();
                    q.pop();
                    for(int j=0;j<len;j++){
                        if(isConnected[xi][j]!=0&&remember[j]==0&&j!=xi){q.push(j);}//将第j行的没有被记录过的元素压入队列中
                    }
                    remember[xi]=1;
                }
                result++;
            }
    }
    return result;
    }
};

通过广度优先搜索的方法得到省份的总数。对于每个城市，如果该城市尚未被访问过，则从该城市开始广度优先搜索，直到同一个连通分量中的所有城市都被访问到，即可得到一个省份。

也就是说在第一层for循环里，如果这一城市没有被处理过，那么这一城市代表的是一个全新的省份，这一次循环就要连根拔起的处理完所有和该城市有关系的城市。

处理的过程中用宽度遍历的方法，也就是将与该城市有联系的只要没处理过的都先一个一个压入队列，然后不断弹出并将弹出的城市的有关系城市且没被处理过的压入队列······

处理完之后将省份数量+1。

拓扑排序算法：

大概就是调用的意思，排序中靠前的点表示先左做，只有先做了这个点才能做后面的点，比如上图只有先做了A才能做B，A和B都做了才能做C，CB都做了才能做D。所以上图的拓扑排序表示为A，B，C，D。

关于拓扑排序的基础思路：首先找出入度为0的点，删除该点带来的影响（不断重复该过程，找，然后删）其处理顺序就是拓扑排序的顺序。

前提不能有环

题目举例：

207. 课程表 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/course-schedule/

方法1：（一个节点的指向节点处理完之后将该节点放入栈中，也就是越早的节点放在栈顶）


class Solution {//拓扑排序
public:
void bianli(vector<vector<int>>&xi,int i,vector<int>&remember,int numCourses,stack<int>&p,bool &result){
    remember[i]=1;
    for(int j=0;j<numCourses;j++){
        if(xi[i][j]!=0&&remember[j]==1){result=false;return;}
        if(xi[i][j]!=0&&remember[j]==0){
            bianli(xi,j,remember,numCourses,p,result);
        }
    }
    remember[i]=2;
    p.push(i);
    return;
}
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>>xi(numCourses,vector<int>(numCourses));
        vector<int>remember(numCourses);
        for(int i=0;i<prerequisites.size();i++){
            xi[prerequisites[i][1]][prerequisites[i][0]]=1;
        }//建立二维向量，其中xi[a][b]=1表示a是b的先修课程
 
        stack<int>p;
        bool result=true;
        for(int i=0;i<numCourses;i++){
            bianli(xi,i,remember,numCourses,p,result);cout<<" "<<i<<" "<<remember[i]<<endl;
            if(result==false){break;}
        }
        return result;
    }
};

拓扑排序成立的前提是不存在环结构。

对于该题来说，返回true的前提是不存在环结构，

设置三种状态：未查询，查询中，已查询。

一旦发现a是b的先修课程，这时候查询b的后续课程发现b是c的先修课程，但是c处于“查询中”也就是c是a的先修课程，这样判断就存在环，也就可以返回false。

方法2：（寻找入度为0的入队列，弹出，将弹出的节点的影响消除，再选择新的入度为0的入队列）


class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>>xi(numCourses,vector<int>(numCourses));
        vector<int>inedges(numCourses);
        queue<int>p;
        unordered_set<int>hashset;
        //int nums=0;//用nums表示处理了多少个课程了，如果有环，那么循环判断之后总有剩下的就是环。
 
        for(int i=0;i<prerequisites.size();i++){
            xi[prerequisites[i][1]][prerequisites[i][0]]=1;
            inedges[prerequisites[i][0]]++;
        }//建立二维向量，其中xi[a][b]=1表示a是b的先修课程
 
        for(int i=0;i<numCourses;i++){
            if(inedges[i]==0){
                p.push(i);
                hashset.insert(i);
            }
        }//首先将所有入度为0的节点放入队列
 
        while(!p.empty()){
            int x=p.front();
            p.pop();
            for(int i=0;i<numCourses;i++){
                if(xi[x][i]==1){inedges[i]--;}
                if(inedges[i]==0&&hashset.count(i)==0){p.push(i);hashset.insert(i);}
            }//将对应的行不为0的对应列入度减1，同时边选择新的入度为0的放入队列。
        }
        return hashset.size()==numCourses;
    }
};

首先选择入度为0的结点A，然后将A及其影响（A的出度边）擦掉，

然后再选择入度为0的点B，然后将B及其影响（B的出度边）擦掉，

......

直到处理完。

我们使用一个队列来进行广度优先搜索。初始时，所有入度为0的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。

在广度优先搜索的每一步中，我们取出队首的节点u：

我们将u放入答案中；

移除u的所有出边，也就是将u的所有相邻节点的入度减少1。如果某个相邻节点v的入度变为0，那么我们就将v放入队列中。

在广度优先搜索的过程结束后。如果处理了在答案里的节点个数等于节点总数，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。

针对无向图的算法：

生成最小生成树（保证连通性且权值最小）

1：kruskal（K算法）

不断选择最小的边，考虑加上会不形成环，如果加上不会形成环，那么就加上否则抛弃并判断下一个。

重点：如何判断有没有环

初始将每个节点看成一个单一的集合，在选择边的过程中查询边的两个点是否在一个集合里，如果不在一个集合里证明添加上这条边不会产生环。然后将变得两个点的集合合并。

2：prim算法

从一个选定的点出发，选择与其邻接的边中最小的，添加点进集合，选择与集合邻接的边中最小的

添加，选择......

3：Dijkstra算法

Dijkstra算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/640868

图*深度遍历(栈，注意拿出来再放进去的小地方)*层序遍历(队列)**拓扑排序(队列和入度数组)**最小生成树的三种算法*_遍历拓扑图中所有节点时所需路径最少的生成树

图的遍历

层序(宽度优先)遍历：

深度优先遍历：（逮着一条路走到黑）

题目举例：

深度遍历：

宽度遍历：

拓扑排序算法：

题目举例：

方法1：（一个节点的指向节点处理完之后将该节点放入栈中，也就是越早的节点放在栈顶）

方法2：（寻找入度为0的入队列，弹出，将弹出的节点的影响消除，再选择新的入度为0的入队列）

针对无向图的算法：

生成最小生成树（保证连通性且权值最小）

1：kruskal（K算法）

2：prim算法

3：Dijkstra算法

图深度遍历(栈，注意拿出来再放进去的小地方)层序遍历(队列)拓扑排序(队列和入度数组)最小生成树的三种算法*_遍历拓扑图中所有节点时所需路径最少的生成树