DFS基础

深度优先搜索算法（英语：Depth-First-Search，缩写为DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

题目

PS:下列题目均来自leetcode中灵神题单

547.省份数量

"""
我们使用for循环遍历每个不同的city作为起点如果该city没有被访问，那么我们就意味着我们遇到了一个新的连通分量,
把res加一，然后用构造函数dfs搜索该连通分量
dfs函数的实现方法是，输入某个顶点，然后递归访问邻接找到与该顶点连通的所有顶点，加入visited标志已访问.
"""
class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        visited=[]
        n=len(isConnected)
        res=0
        def dfs(vertex):
            for i in range(n):
                if isConnected[vertex][i]==1 and i not in visited:
                    visited.append(i)
                    dfs(i)

        for i in range(n):
            if i not in visited:
                dfs(i)
                res+=1
        return res

1971. 寻找图中是否存在路径

#超出内存限制了...
"""
把edge转换成邻接矩阵
然后按照上面的题目解法只搜索有关source的连通分量
最后检查source的连通分量中有没有destination
"""
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        G=[[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            G[i][i]=1
        for v,vn in edges:
            G[v][vn]=1
            G[vn][v]=1
        def dfs(vertex):
            for i in range(n):
                if G[vertex][i]==1 and i not in visited:
                    visited.add(i)
                    dfs(i)
        visited=set()
        dfs(source)
        return destination in visited

#把邻接矩阵换成邻接表就通过了(虽然很慢)
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        if len(edges)==0:
            return source==destination
        G=defaultdict(list)
        for v,vn in edges:
            G[v].append(vn)
            G[vn].append(v)
        def dfs(vertex):
            for i in G[vertex]:
                if  i not in visited:
                    visited.add(i)
                    dfs(i)
        visited=set()
        dfs(source)
        return destination in visited

#官方解法
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        if len(edges)==0:
            return source==destination
        G=defaultdict(list)
        for v,vn in edges:
            G[v].append(vn)
            G[vn].append(v)
        def dfs(vertex):
            if vertex==destination:
                return True
            visited.add(vertex)
            for i in G[vertex]:
                if  i not in visited and dfs(i):
                    return True
            return False
        visited=set()
        return dfs(source)