记录DFS和递归解决LC第547省份问题（本质是图的连通分量）

1.DFS（深度优先搜索）：一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

2.递归的三大核心：一.清楚这个递归函数的功能是做什么

二.清楚递归的结束条件，否则陷入死循环

三.写一个等价表达式完成对递归的调用

3.这个题涉及到图的知识：

图（graph）：图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中的顶点的集合，E是图G中边的集合。

顶点(Vertex)：图中的数据元素。线性表中我们把数据元素叫元素，树中将数据元素叫结点。

边：顶点之间的逻辑关系用边来表示，边集可以是空的。

无向边(Edge)：若顶点V1到V2之间的边没有方向，则称这条边为无向边。

无向图(Undirected graphs)：图中任意两个顶点之间的边都是无向边。（A,D）=（D,A）

对于无向图G来说，G1=（V1,{E1}），其中顶点集合V1={A,B,C,D}；边集和E1={（A,B），（B,C），（C,D），（D,A），（A,C）}

有向边：若从顶点V1到V2的边有方向，则称这条边为有向边，也称弧(Arc)。用<V1,V2>表示，V1为狐尾(Tail)，V2为弧头(Head)。（V1，V2）≠（V2，V1）。

有向图(Directed graphs)：图中任意两个顶点之间的边都是有向边。

注意：无向边用“（）”，而有向边用“< >”表示。

简单图：图中不存在顶点到其自身的边，且同一条边不重复出现。

无向完全图：无向图中，任意两个顶点之间都存在边。

有向完全图：有向图中，任意两个顶点之间都存在方向互为相反的两条弧。

稀疏图：有很少条边。

稠密图：有很多条边。

权（Weight）：与图的边或弧相关的数。

网（Network）：带权的图。

子图（Subgraph）：假设G=（V,{E}）和G‘=（V',{E'}），如果V'包含于V且E'包含于E，则称G'为G的子图。

度（Degree）：无向图中，与顶点V相关联的边的数目。有向图中，入度表示指向自己的边的数目，出度表示指向其他边的数目，该顶点的度等于入度与出度的和。

路径的长度：一条路径上边或弧的数量。
连通图：图中任意两个顶点都是连通的。

连通分量：无向图中的极大连通子图。（子图必须是连通的且含有极大顶点数）。图1有两个连通分量
强连通分量：有向图中的极大强连通子图。

生成树：无向图中连通且n个顶点n-1条边叫生成树。

有向树：有向图中一顶点入度为0其余顶点入度为1。

森林：一个有向图由若干棵有向树构成生成森林。

了解清楚上面的3个数据结构知识点就能完成这道题了。

总思路：遍历所有城市，对于每个城市，如果该城市尚未被访问过，则从该城市开始深度优先搜索，通过矩阵 isConnected 得到与该城市直接相连的城市有哪些，这些城市和该城市属于同一个连通分量，然后对这些城市继续深度优先搜索，直到同一个连通分量的所有城市都被访问到，即可得到一个省份。遍历完全部城市以后，即可得到连通分量的总数，即省份的总数

结合代码与注释搞懂：

class Solution {
    public int findCircleNum(int[][] isConnected) {
         //城市数量
         int length=isConnected.length;
         //表示哪个城市被访问过
         boolean[]visited=new boolean[length];//开始都为0，false
         int count=0;//省份数量
         for(int i=0;i<length;i++){
             //如果当前城市未被访问过，就说明是个新省分，count+1，
             //并且和这个城市相连的都标记为访问过的，也就是统一省分的
             if(!visited[i]){//先是第i个城市未访问，然后进入递归，去找下一个
             dfs(isConnected,visited,i);
             count++;

             }
         }
         return count;
    }

    public void dfs(int[][] isConnected,boolean[]visited,int i){
        for(int j=0;j<isConnected.length;j++){
            if(isConnected[i][j]==1&&!visited[j]){//循环条件
                //如果第i和第j个城市是相连的且第j个城市未访问，说明他们是同一个省份，把它标记为已访问过
                visited[j]=true;
                //然后继续查找与第j个城市相连的城市
                dfs(isConnected,visited, i); //结合for循环就是等价表达式了           
                }
        }
    }
}