深度优先搜索 | 547. Friend Circles

本文主要是介绍深度优先搜索 | 547. Friend Circles，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

给定一个二维的 0-1 矩阵，如果第 (i, j) 位置是 1，则表示第 i 个人和第 j 个人是朋友。已知朋友关系是可以传递的，即如果 a 是 b 的朋友，b 是 c 的朋友，那么 a 和 c 也是朋友，换言之这三个人处于同一个朋友圈之内。求一共有多少个朋友圈。

输入输出样例输入是一个二维数组，输出是一个整数，表示朋友圈数量。因为朋友关系具有对称性，该二维数组为对称矩阵。同时，因为自己是自己的朋友，对角线上的值全部为 1。
Input: [[1,1,0], [1,1,0], [0,0,1]]
Output: 2
在这个样例中，[1,2] 处于一个朋友圈，[3] 处于一个朋友圈。

二、题解

和上一题类似，包含一个主函数遍历所有点，判断是否可以作为搜索点起点，另外还包括一个辅助函数，用于深度优先搜索点递归调用。上一道题中，每一个位置表示一个节点，上下左右位置节点为相邻节点，而这里第i行与第i列是同一个人，为一个节点，相邻节点为第j列和j行。
然后这道题和上一道题类型一致了就。
而深度优先搜索的递归的写法有两种方式：

先判断合理性再递归调用（判断函数写在递归调用前）
先搜索再在下一次搜索开始时判断合法性（判断放在辅函数第一行）

三、代码

这里我们采用第一种写法：

//主函数
Int findCircle(vector<Vector<int>>& friends){Int n = friends.size(),count=0;vector<bool> visited(n,false);for(int I = 0;I<friends.size();I++){If(visited[I]==false){Dsf(friends,I,visited);++count;}}return count;
}//辅函数
void dfs（vector<vector<int>>& friends,int i,vector<bool>& visited){Visited[i] = true;for(int k=0;k<friends.size();++k){If(friends[i][k]==1 && !visited[k]){Dfs(friends,k,visited);}}
}