Algorithm tree ----- DFS、BFS
一个多叉树结构如下图所示:
- 创建如图所示的数据结构,用镶套字典实现。
# 创建多叉树
d = {"x": {"a": {"b":{}, "c":{}, "d": {}}, "e":{"f":{"g": {}, "k": {}}}}}
- 深度优化遍历
# dfs 递归实现
ans = -1
nodes = []
def dfs(d, deep):
global ans
if len(d.keys()) == 0:
ans = max(ans, deep)
return
else:
for k in d.keys():
nodes.append(k)
dfs(d[k], deep + 1)
# 调用
dfs(d, 0)
print("Tree depth: {}".format(ans))
print("Path: {}".format("->".join(nodes)))
## output:
## Tree depth: 4
## Path: x->a->b->c->d->e->f->g->k
# dfs 非递归,通过栈实现
ans = 0
nodes = []
def dfs(d):
global ans
stack = []
key = list(d.keys())[0]
stack.append(d)
while len(stack):
d = stack[-1]
if len(list(d.values())[0]):
ans += 1
stack.pop()
for k, v in d.items():
r_v = list(v.items())
r_v.reverse()
for k2, v2 in dict(r_v).items():
stack.append({k2: v2})
nodes.append(k)
# 调用
dfs(d)
print("Tree depth: {}".format(ans))
print("Path: {}".format("->".join(nodes)))
## output:
## Tree depth: 4
## Path: x->a->b->c->d->e->f->g->k
- 广度优先遍历
# bfs 非递归,通过队列实现
ans = 0
nodes = []
def bfs(d):
global ans
queue = []
key = list(d.keys())[0]
queue.append(d)
while len(queue):
d = queue[0]
if {} not in queue:
ans += 1
queue.remove(d)
for k, v in d.items():
queue.append(v)
nodes.append(k)
# 调用
bfs(d)
print("Tree depth: {}".format(ans))
print("Path: {}".format("->".join(nodes)))
## output
## Tree depth: 4
## Path: x->a->e->b->c->d->f->g->k