欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[笔记]《算法图解》第六章 广度搜索优先

程序员文章站 2022-05-23 10:05:24
...

广度优先搜索-

  • 广度优先搜索 是一种图算法。
  • 解决最短路径问题的算法被称为广度优先搜索。
  • 图:
    • 图由节点和边组成。一个节点可能与众多节点直接项链,这些节点被称为邻居。
    • 可以使用图模拟不同的东西是如何相连的。
  • 广度优先搜索是一种用于图的查找算法,可以帮助回答两类问题。

    第一,从节点A出发,有前往节点B的路径吗?
    第二,从节点A出发,前往节点B的哪条路径最短?

  • 在广度优先搜索的执行过程中,搜索范围从起点开始逐渐向外延伸,即先检查一度关系,再检查二度关系。
  • 广度优先搜索的运行时间为

    O(人数 + 边数),这通常写作O(V + E),其中V为顶点(vertice)数,E为边数。

队列和栈

  • 队列是一种先进先出(First In First Out,FIFO)的数据结构
  • 栈是一种后进先出(Last In First Out,LIFO)的数据结构

  • 有指向关系的这被称为有向图(directed graph),其中的关系是单向的。
  • 无向图(undirected graph)没有箭头,直接相连的节点互为邻居。

代码实现广度搜索优先

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:
                search_queue += graph[person]
                searched.append(person)
                #将这个人标记为检查过
                return False
search("you")

转载于:https://www.cnblogs.com/everfight/p/grokking_algorithms_note_6.html