深度优先搜索（DFS）-- Python

深度优先搜索（DFS）-- Python

DFS(深度优先搜索)：是一种对图进行搜索的算法。
借助栈：先进后出的性质实现
深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。

定义一个图：

graph = {
    "A":["B","C"],
    "B":["A","C","D"],
    "C":["A","B","D","E"],
    "D":["B","C","E","F"],
    "E":["C","D"],
    "F":["D"]
}

下面的代码：

graph = {
    "A":["B","C"],
    "B":["A","C","D"],
    "C":["A","B","D","E"],
    "D":["B","C","E","F"],
    "E":["C","D"],
    "F":["D"]
}

def DFS(graph,s):
    stack = []
    stack.append(s)
    seen = set()
    seen.add(s)
    parent = {s:None}

    while stack:
        vertex = stack.pop()
        nodes = graph[vertex]
        for m in nodes:
            if m not in seen:
                stack.append(m)
                seen.add(m)
                parent[m] = vertex
        print(vertex)
    return parent

if __name__ == "__main__":
    result = DFS(graph,"A")
    print(result)

"""
results:
	A
	C
	E
	D
	F
	B
	{'A': None, 'B': 'A', 'C': 'A', 'D': 'C', 'E': 'C', 'F': 'D'}
"""