广度优先和深度优先算法实现LeetCode547朋友圈（Python）

针对本题，大部分题解是使用的深度优先算法实现的，本文提供了广度优先的解决方案。

1、深度优先

            
              ​
class Solution:
    def findCircleNum(self, M):
        visited, ans = set(), 0

        def dfs(i):
            for j in range(len(M[i])):
                if M[i][j] and j not in visited:
                    visited.add(j)
                    dfs(j)

        for i in range(len(M)):
            if i not in visited:
                dfs(i)
                ans += 1
        return ans

​
            
          

2、广度优先

            
              class Solution:
    def findCircleNum(self, M):
        queen = []
        visited = set()
        ans = 0
        def bfs(i):
            queen.append(i)
            while queen:
                i = queen[0]
                queen.pop(0)
                for j in range(len(M[i])):
                    if M[i][j] and j not in visited:
                        visited.add(j)
                        queen.append(j)

        for i in range(len(M)):
            if i not in visited:
                bfs(i)
                ans += 1
        return ans