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

Lacie ·

更新时间:2024-11-13

· 675 次阅读

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即可

您可能感兴趣的文章:基于python模拟TCP3次握手连接及发送数据基于Python模拟浏览器发送http请求python产生模拟数据faker库的使用详解Python中使用aiohttp模拟服务器出现错误问题及解决方法Python模拟登录和登录跳转的参考示例Python Tkinter实例——模拟掷骰子Python使用Selenium模拟浏览器自动操作功能如何利用Python动态模拟太阳系运转

dfs Python

1024 个赞