这是《python算法教程》的第5篇读书笔记。这篇笔记的主要内容为运用DFS（深度优先搜索，depth first search）对图（邻接字典）进行遍历。

DFS简介

在解决问题的时候，需要对整个图进行遍历，以获取整个图的节点信息。此时遍历的思路是根据当前访问的点，访问其邻接点，最终使得整个图的节点均被访问。此时，访问邻接节点的策略有DFS（深度优先搜索）和BFS（广度优先搜索）。DFS是先访问当前节点的一个邻接节点，再继续访问该邻接节点的邻接节点，直到访问的邻接节点没有邻接节点。之后再访问上一层节点的另外一个邻接节点，然后继续访问这另一个邻接节点的邻接节点。

代码示例

以下将根据下图给出递归版和迭代版的深度优先搜索代码。

DAG.JPG

递归版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

#迭代版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)