基于python模拟bfs和dfs代码实例

BFS

\"\"\"
# @Time  : 2020/11/8
# @Author : Jimou Chen
\"\"\"


# 广搜
def bfs(graph, start):
  queue = [start] # 先把起点入队列
  visited = set() # 访问国的点加入
  visited.add(start)

  while len(queue):
    vertex = queue.pop(0)
    # 找到队列首元素的连接点
    for v in graph[vertex]:
      if v not in visited:
        queue.append(v)
        visited.add(v)
    # 打印弹出队列的该头元素
    print(vertex, end=\' \')


if __name__ == \'__main__\':
  graph = {
    \'A\': [\'B\', \'D\', \'I\'],
    \'B\': [\'A\', \'F\'],
    \'C\': [\'D\', \'E\', \'I\'],
    \'D\': [\'A\', \'C\', \'F\'],
    \'E\': [\'C\', \'H\'],
    \'F\': [\'B\', \'H\'],
    \'G\': [\'C\', \'H\'],
    \'H\': [\'E\', \'F\', \'G\'],
    \'I\': [\'A\', \'C\']
  }

  bfs(graph, \'A\')

A B D I F C H E G
Process finished with exit code 0

DFS

\"\"\"
# @Time  : 2020/11/8
# @Author : Jimou Chen
\"\"\"


# 深搜
def dfs(graph, start):
  stack = [start]
  visited = set()
  visited.add(start)

  while len(stack):
    vertex = stack.pop() # 找到栈顶元素
    for v in graph[vertex]:
      if v not in visited:
        stack.append(v)
        visited.add(v)

    print(vertex, end=\' \')


if __name__ == \'__main__\':
  graph = {
    \'A\': [\'B\', \'D\', \'I\'],
    \'B\': [\'A\', \'F\'],
    \'C\': [\'D\', \'E\', \'I\'],
    \'D\': [\'A\', \'C\', \'F\'],
    \'E\': [\'C\', \'H\'],
    \'F\': [\'B\', \'H\'],
    \'G\': [\'C\', \'H\'],
    \'H\': [\'E\', \'F\', \'G\'],
    \'I\': [\'A\', \'C\']
  }

  dfs(graph, \'E\')

E H G F B A I D C
Process finished with exit code 0

总结

很明显一个用了队列，一个用了栈

利用python语言优势，只需改动pop即可

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。