算法快学笔记(十二):图的广度优先搜索(BFS-Breadth First Search)

栏目: 编程工具 · 发布时间: 5年前

内容简介:广度优先搜索(BFS)是一个经典的图算法,该算法能够找出两样东西之间的最短距离!使用广度优先搜索可以:要说明的是,广度优先搜索是一种用于图的查找算法,可帮助回答两类问题。

1. 介绍

广度优先搜索(BFS)是一个经典的图算法,该算法能够找出两样东西之间的最短距离!使用广度优先搜索可以:

  • 编写国际跳棋AI,计算最少走多少步就可获胜;
  • 编写拼写检查器,计算最少编辑多少个地方就可将错拼的单词改成正确的单词,如将READED改为READER需要编辑一个地方;
  • 根据你的人际关系网络找到关系最近的医生。

要说明的是,广度优先搜索是一种用于图的查找算法,可帮助

回答两类问题。

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

2. 原理说明

假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。在Facebook,你与芒果销售商有联系吗?为此,你可在朋友中查找,这种查找很简单。首先,创建一个朋友名单,假设你没有朋友是芒果销售商,那么你就必须在朋友的朋友中查找,检查名单中的每个人时,你也都将其朋友加入名单

算法快学笔记(十二):图的广度优先搜索(BFS-Breadth First Search)

这样一来,你不仅在朋友中查找,还在朋友的朋友中查找。别忘了,你的目标是在你的人际关系网中找到一位芒果销售商。因此,如果Alice不是芒果销售商,就将其朋友也加入到名单中。这意味着你将在她的朋友、朋友的朋友等中查找。使用这种算法将搜遍你的整个人际关系网,直到找到芒果销售商。这就是广度优先搜索算法。

对于BFS要解决的第一个问题很容易处理,只要遍历朋友列表,就能得知朋友圈中到底有没有芒果销售商,下面来看看如何找到哪个销售商和你的关系是最好的。

2.1 查找最亲密的销售商

为了便于度量关系的亲密度,我们假设朋友是一度关系,朋友的朋友是二度关系…,一度关系胜过二度关系,二度关系胜过三度关系,以此类推.

为了确保找到的销售商关系是最亲密的,你应先在一度关系中搜索,确定其中没有芒果销售商后,才在二度关系中搜索。

BFS算法的执行流程也就是**搜索范围从起点开始逐渐向外延伸,即先检查一度关系,再检查二度关系。**

在查找列表的过程中,有点需要注意,因为1度关系比二度关系先添加,二度关系比三度关系先添加,因此只有按添加顺序查找,才能找到最短路径。此处可以使用队列实现。

3. 算法实现

# -*- coding:utf-8 -*-
# @Author:sunaihua 
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"] = ["bob"]

# 节点对象,用来标识各个节点之间的父子关系
# name:字符串类型,代表节点名称
# parent:Node类型
class Node:
    def __init__(self, name, parent):
        self.name = name
        self.parent = parent

    def __str__(self):
        return self.name


def is_seller(friend):
    return friend.name[-1] == 'm'

# 通过bfs找到最近的节点
def bfs_search():
    search_queue = deque()
    # 初始化任务队列
    search_queue += [Node(name=friend, parent=Node(name='you', parent=None)) for friend in graph['you']]
    searchrd = []
    while search_queue:
        # 每次都弹出队列最左面的元素,且是关系最亲密的。
        friend = search_queue.popleft()
        # 防止重复搜索
        if friend not in searchrd:
            if is_seller(friend):
                print "has seller,%s is seller" % (friend)
                return friend

            else:
                # 将当前friend的所有friend添加到队列的最右面
                search_queue += [Node(name=f, parent=friend) for f in graph[friend.name]]
    return None

# 根据超找到的对象,打印路径
def print_path(node):
    node_name_stack = []
    node_name_stack.append(node.name)
    parent_node = node.parent
    # 生成节点名称列表
    while parent_node:
        node_name_stack.append(parent_node.name)
        parent_node = parent_node.parent
    # 反转列表
    node_name_stack.reverse()
    # 打印路径
    print "friends path:","--->".join(node_name_stack)


if __name__ == '__main__':
    target = bfs_search()
    print_path(target)

4. 运行时间

如果你在你的整个人际关系网中搜索芒果销售商,就意味着你将沿每条边前行(记住,边是

从一个人到另一个人的箭头或连接),因此运行时间至少为O(边数)。

你还使用了一个队列,其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的,即为O(1),因此对每个人都这样做需要的总时间为O(人数)。所以,广度优先搜索的运行时间为

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

5. 总结

  • 广度优先搜索主要用来解决最短路径问题
  • FS算法的执行流程是搜索范围从起点开始逐渐向外延伸,即先检查一度关系,再检查二度关系…
  • 时间复杂度为O(V + E)

以上所述就是小编给大家介绍的《算法快学笔记(十二):图的广度优先搜索(BFS-Breadth First Search)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

虚拟经济学

虚拟经济学

威利•莱顿维塔、爱德华•卡斯特罗诺瓦 / 崔毅 / 中国人民大学出版社 / 2015-6 / 49.00元

电子游戏中也存在 “看不见的手”吗?玩虚拟游戏能够创造真实价值吗?为什么现实世界需要虚拟经济?经济学作为一门成熟的学科,起源于对农业、制造业和商业的探究,曾经作为解决饥饿、就业这些人类所面对的真实问题的方法。然而,在虚拟世界,最为稀缺的资源不再是食物和住所,而是人类的关注度。一些基于农业、制造业和商业存在的经济学理论、概念依然适用于游戏中的虚拟世界,比如最为人们所熟知的“看不见的手”这一概念。同时......一起来看看 《虚拟经济学》 这本书的介绍吧!

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

html转js在线工具
html转js在线工具

html转js在线工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试