你知道吗？广度优先与深度优先只有这一个区别！
你好呀，我是阿德。
我最近在复习二叉树相关内容，看到二叉树的遍历算法，电光火石之间，我突然发现了广度优先与深度优先的本质区别，可以让你一分钟记住这两个算法。
广度优先搜索和深度优先搜索一样，都是可以对二叉树或图进行搜索的算法，都是从起点开始沿着边搜索，一直搜索直到找到指定节点(即终点)。
在此过程中每走到一个节点，就会判断一次它是否为终点。
两者的区别就是，广度优先搜索会根据离起点的距离，按照从近到远的顺序对各节点进行搜索。而深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条路径。
-
贝尔曼-福特算法（(Bellman-Ford） -
狄克斯特拉算法（Dijkstra） -
A* 算法（A-Star）
graph = {}graph["A"] = ["B", "D", "F"]graph["B"] = ["C", "E"]graph["D"] = ["C"]graph["F"] = ["G", "H"]graph["C"] = []graph["E"] = []graph["G"] = []graph["H"] = []
deque
来创建一个双端列表，可以实现在列表两端添加(append)和弹出(pop)元素。
from collections import dequesearch_queue = deque() # 创建一个节点列表search_queue += graph["A"] # 表示将"A"的相邻节点都添加到节点列表中
searched
数组来保存搜索过的节点，防止同一个节点被多次搜索。
from collections import dequedef search(start_node):search_queue = deque()search_queue += graph[start_node]searched = [] # 这个数组用于记录检查过的节点while search_queue: # 只要节点列表不为空node = search_queue.popleft() # 取出节点列表中最左边的节点print(node, end=' ') # 打印出当前节点if not node in searched: # 如果这个节点没检查过if node == 'G': # 检查这个节点是否为终点"G"print("\nfind the destination!")return Trueelse:search_queue += graph[node] # 将此节点的相邻节点都添加到节点列表中searched.append(node) # 将这个节点标记为检查过# 如果节点列表为空仍没找到终点，则返回Falsereturn Falseprint(search("A"))
B D F C E C Gfind the destination!True
node = search_queue.popleft() # 取出节点列表中最左边的节点node = search_queue.pop() # 取出节点列表中最右边的节点F H G D C Bfind the destination!True
阿德最新文章不错过
程序员阿德
985非科班程序员，自学转行计算机，专注于分享计算机基础知识，从底层提升你的码力。
Official Account