深度优先搜索和广度优先搜索

搜索

• 每个节点都要访问一次
• 每个节点仅仅要访问一次
• 对于节点的访问顺序不限
  • 深度优先：depth fist search
  • 广度优先：breadth first search

深度优先搜索算法：

• DFS（Depth-First-Search）
• 是一种用于遍历或搜索树或图的算法。
• 这个算法会尽可能深地搜索树的分支。
• 当节点 v 的所在边都已被搜寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个过程反复进行直到所有节点都被访问为止。
• 是图论中的经典算法，利用深度优先搜索算法可以产生目标图的拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如无权最长路径问题等等。

实现方法：

1. 首先将根节点放入 stack 中。
2. 从 stack 中取出第一个节点，并检验它是否为目标。如果找到目标，则结束搜寻并回传结果。否则将它某一个尚未检验过的直接子节点加入 stack 中。
3. 重复步骤 2.
4. 如果不存在未检测过的直接子节点。将上一级节点加入 stack 中。重复步骤 2。
5. 重复步骤 4。
6. 若 stack 为空，表示整张图都检查过了—亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

代码模版

递归写法：

visited = set() 

def dfs(node, visited):
  if node in visited: # terminator
    # already visited 
      return 

  visited.add(node) 

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

非递归写法：

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 = generate_related_nodes(node)     
    stack.push(nodes) 

  # other processing work 
  ...

广度优先搜索算法：

• BFS（Breadth First Search），又译作宽度优先搜索，或横向优先搜索
• 是一种图形搜索算法。
• BFS 是从根节点开始，沿着树的宽度遍历树的节点。
• 如果所有节点均被访问，则算法中止。
• 广度优先搜索的实现一般采用 open-closed 表。
• 是一种盲目搜索法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能地址，彻底地搜索整张图，直到找到结果为止。
• 从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实现里，其邻居节点尚未被检验过的节点会被放置在一个称为 open 的容器中（例如队列或链表），而被检验过的节点，则被放置在被称为 closed 的容器中。（open-closed 表）

实现方法：

1. 首先将根节点放入队列中。
2. 从队列中取出第一个节点，并检验它是否为目标。
   • 如果找到目标，则结束搜索并回传结果。
   • 否则将它所有尚未检验过的直接子节点加入队列中。
3. 若队列为空，表示整张图都检查过了—亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。
4. 重复步骤 2。

代码模版

def bfs(graph, start, end):
  visited = set()
  queue = [] 
  queue.append([start]) 

  while queue: 
    node = queue.pop() 
    visited.add(node)
     process(node) 
    nodes = generate_related_nodes(node) 
    queue.push(nodes)

  # other processing work 
  ...