深度优先搜索算法

介绍

深度优先搜索(DFS, Depth First Search)是一个针对图和树的遍历算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

执行顺序

1. 先选出A开始
2. 看A可以到达的是B，C stack = B，C
3. 选择到达C，C可以到达的是A，B，D，E，其中A，B已经遇见过可选，D，E stack = B，D，E
4. 选择E，E可以达到C，D，都已经遇见stack= B，D
5. 后退到D，可以到达B，C，E，F，其中B，C，E都见过选择F，stack = B
6. 后退到B，这样全部都被搜寻过了

程序示例

graph = {
    "A" : ["B", "C"],
    "B" : ["A", "C", "D"],
    "C" : ["A", "B", "D", "E"],
    "D" : ["B", "C", "E", "F"],
    "E" : ["C", "D"],
    "F" : ["D"]
}
'''
            A
           / \
          B---C
           \ / \
            D---E
           /
          F  
step1:A
    stack = B C
    sen = A
    already = A
step2:C
    stack = B D E
    sen = A B C D E
    already = A C
step3:E
    stack = B D 
    sen = A B C D E
    already = A C E
step4:E
    stack = B F
    sen = A B C D E F
    already = A C E D
'''
def DFS(graph, startNode):
    stack = []
    already = []
    stack.append(startNode)
    seen = set()
    seen.add(startNode)

    while (len(stack) > 0):
        vertex = stack.pop()
        already.append(vertex)
        print(vertex)
        nodes = graph[vertex]
        for w in nodes:
            if w not in seen:
                stack.append(w)
                seen.add(w)
        print('stack',stack)
        print('seen',seen)

DFS(graph, "A")