解决最短路径问题的算法被称为广度优先搜索。
图是什么？图模拟一组连接，由节点（node）和边（edge）组成。一个节点可能与众多节点直接相连，这些节点被称为邻居。
问题：假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他。在通讯录中，你与芒果销售商有联系吗？为此，你可在朋友中查找。
找橘子商示例代码：
from collections import deque def search(name): search_queue = deque() search_queue += graph[name] #这个数组用于记录检查过的人 searched = [] while search_queue: #取出第一个人 person = search_queue.popleft() #仅当这个人没检查过时才检查 if not person in searched: #检查是否芒果商 if person_is_seller(person): print (person + " is a mango seller") return True else: #继续搜索s_q = s_q + graph[person] 后面一项是person的邻居 search_queue +=graph[person] #将这个人标记为检查过 searched.append(person) print("not found") return False def person_is_seller(name): return name[-1] == ‘m‘ #测试 graph ={} graph["you"] = ["alice","bob","c"] graph["alice"] =[] graph["bob"] = [] graph["c"] = [] search("you")
广度优先搜索的运行时间为O(人数 + 边数)，这通常写作O(V + E)，其中V为顶点（vertice）数，E为边数。
原文：https://www.cnblogs.com/wmxnlfd/p/10512762.html