不会飞的章鱼

熟能生巧，勤能补拙；念念不忘，必有回响。

算法训练营-深度优先搜索、广度优先搜索的实现和特性

发表于 更新于 分类于
本文字数： 877 阅读时长 ≈ 1 分钟

搜索-遍历

  • 每个节点都要访问一次
  • 每个节点仅仅要访问一次（不做无用功）
  • 对于节点的访问顺序不限：dfs / bfs

示例代码

DFS算法模板

1
2
3
4
5
6
7
8
9
10
11
12
def dfs(node):
    if node in visited:
        # already visited
        return
    
    visited.add(node)

    # process current node
    # ... logic here

    dfs(node.left)
    dfs(node.right)

DFS代码-递归写法

1
2
3
4
5
6
7
8
9
visited = set()

def dfs(node,visited):
    visited.add(node)
    # process current node here
    ...
    for next_node in node.children():
        if not next_node in visited:
            dfs(next node,visited)

DFS代码-非递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def DFS(self,tree):
    if tree.root is None:
        return []
    
    visited,stack = [].[tree.root]

    while stack:
        node = stack.pop()
        visited.add(node)

        process(node)
        nodes = generagte_related_nodes(node)
        stack.push(nodes)

    # other processing work

BFS代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def BFS(graph,start,end):
    queue = []
    queue.append([start])
    visited.add(start)

    while queue:
        node = queue.pop()
        visited.add(node)

        process(node)
        nodes = generagte_related_nodes(node)
        queue.push(nodes)

    # other processing work

DFS和BFS遍历顺序

参考链接

https://visualgo.net/en

------ 本文结束------
如果本篇文章对你有帮助，可以给作者加个鸡腿~(*^__^*)，感谢鼓励与支持！