算法图解第六章广度优先搜索读书笔记

1. 图由节点和边组成.一个节点可能与众多节点直接相连,这些节点被称为邻居.
2. 广度优先搜索是一种用于图的查找算法,可以帮助回答两类问题: 1)从节点A出发,有前往节点B的路径吗? 2)从节点A出发,前往节点B的哪条路径最短?
3. 有向图和无向图(没有箭头,直接相连的节点互为邻居)
4. 拓扑排序
5. 树是一种特殊的图
6. 广度优先搜索算法

7. from collections import deque
   graph = {}
   graph["you"] = ["alice", "bob", "claire"]
   graph["bob"] = ["anuj", "peggy"]
   graph["alice"] = ["peggy"]
   graph["claire"] = ["thom", "jonny"]
   graph["anuj"] = []
   graph["peggy"] = []
   graph["thom"] = []
   graph["jonny"] = []
   
   def search(name):
       search_queue = deque()
       search_queue += graph[name]
       searched = []
       while search_queue:
           person = search_queue.popleft()
           if person not in searched:
               if person_is_seller(person):
                   print(person + " is a mango seller!")
                   return True
               else:
                   search_queue += graph[person]
                   searched.append(person)
       return False
   
   
   def person_is_seller(nname):
       return nname[-1] == 'm'
   
   search("you")