钥匙和房间-图论841-python

没看答案。
图论的广度优先搜索（BFS），类似树结构的BFS，都是利用队列实现的。

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        visited = [True] + [False] * (n-1) # 用于判断某个房间在之前是否已经访问过，防止死循环
        queue = [i for i in rooms[0]]

        while queue:
            for _ in range(len(queue)):
                key = queue[0]
                queue.pop(0)

                if not visited[key]:
                    visited[key] = True # 进入（访问）该房间

                    for k in rooms[key]: # 拿走房间中所有未访问房间的钥匙
                        if not visited[k]:
                            queue.append(k)

        # 若存在未被访问的房间，则False，否则为True
        for flag in visited:
            if not flag:
                return False
        else:
            return True

图论的深度优先搜索（DFS），类似树结构的DFS，利用递归实现（也可以用栈实现）。

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        visited = [True] + [False] * (n-1) # 用于判断某个房间在之前是否已经访问过，防止死循环
        
        def dfs(keys): 
            for key in keys: # 拿走房间中所有未访问房间的钥匙
                if not visited[key]:
                    visited[key] = True # 进入（访问）该房间
                    dfs(rooms[key])
        
        dfs(rooms[0])
            
        # 若存在未被访问的房间，则False，否则为True
        for flag in visited:
            if not flag:
                return False
        else:
            return True