dfs(easy)
2021-01-02 本文已影响0人
warManHy
使用栈stack
graph = {
a: [a1,b],
a1: [a2],
b: [],
a2: []
}
----------
父节点a,找个子节点a1,压入栈,判断子节点还有子a2没,有继续压入,没有了,弹出 a2,a1,a
从父节点继续a, 子节点b 没有了,输出b,a
都标记了,结束;
-----------
def dfs(graph, s):
stack = []
stack.append(s)
seen = set()
seen.add(s)
while len(stack):
v = stack.pop()
nodes = graph[v]
for w in nodes:
if w not in seen:
stack.append(w)
seen.add(w)
break
print v