《python算法教程》Day5 - DFS遍历图（邻接字典）DFS简介代码示例

#递归版DFS
def dfs(G,s,S=None,res=None):
    if S is None:
        #储存已经访问节点
        S=set()
    if res is None:
        res=[]
    res.append(s)
    S.add(s)
    for u in G[s]:
        if u in S:
            continue
        S.add(u)
        dfs(G,u,S,res)
    return res

#有向无环图的邻接字典
G={
    'a':{'b','f'},
    'b':{'c','d','f'},
    'c':{'d'},
    'd':{'e','f'},
    'e':{'f'},
    'f':{}
}

res=dfs(G,'a')
print(res)

#迭代版DFS
def dfs(G,s):
    Q=[]
    S=set()
    Q.append(s)
    while Q:
        u=Q.pop()
        if u in S:
            continue
        S.add(u)
        Q.extend(G[u])
        yield u
#有向无环图的邻接字典
G={
    'a':{'b','f'},
    'b':{'c','d','f'},
    'c':{'d'},
    'd':{'e','f'},
    'e':{'f'},
    'f':{}
}

res=list(dfs(G,'a'))
print(res)