图
图模拟一组连接，由节点和边组成，一个节点可能与众多节点直接相连，这些节点被称为邻居。

广度优先搜索
广度优先搜索是一种图算法，主要解决两种问题：
       1.从节点A出发，有前往节点B的路径吗？
       2.从节点A出发，前往节点B的哪条路径最短？


芒果销售商问题
假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他，而找这个销售商最好的办法就是在你的关系网中寻找，下面使用广度优先搜索实现这个问题：

[Python] 纯文本查看 复制代码

from collections import deque


def do_map():
    """实现图"""
    graph = dict()
    graph["you"] = ["zhangsan", "lisi", "wangwu"]
    graph["zhangsan"] = ["xiaoming", "xiaohong"]
    graph["lisi"] = ["liniu", "you"]
    graph["wangwu"] = ["wangniu", "mango"]
    graph["xiaoming"] = []
    graph["xiaohong"] = []
    graph["liniu"] = []
    graph["wangniu"] = []
    graph["mango"] = []

    return graph


def check_person(person):
    """检查是否是销售商"""
    if person == 'mango':   # 给一个简单的条件，只要名字是mango的就是销售商
        return True
    return False


def search(name, graph):
    """广度优先搜索-销售商"""
    search_queue = deque()  # 创建队列
    search_queue += graph[name]  # 将一度关系加入队列

    searched = []  # 准备一个已经搜寻过销售商的列表

    # 只要队列不为空，
    while search_queue:
        person = search_queue.popleft()  # 取出第一个人

        # 判断该人是否已经检查过了
        if person not in searched:
            # 判断该数据是否是要搜索的销售商
            if check_person(person):
                print('%s is a mango seller' % person)
                return True

            else:
                # 不是，将这个人的朋友即二度关系加入队列
                search_queue += graph[person]

                # 将这个人标记为检查过
                searched.append(person)

    # 队列查完都没有就说明没找到
    return False


if __name__ == '__main__':
    graph = do_map()
    print(search('you', graph))

图
图模拟一组连接，由节点和边组成，一个节点可能与众多节点直接相连，这些节点被称为邻居。

广度优先搜索
广度优先搜索是一种图算法，主要解决两种问题：
       1.从节点A出发，有前往节点B的路径吗？
       2.从节点A出发，前往节点B的哪条路径最短？


芒果销售商问题
假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他，而找这个销售商最好的办法就是在你的关系网中寻找，下面使用广度优先搜索实现这个问题：

[Python] 纯文本查看 复制代码

from collections import deque


def do_map():
    """实现图"""
    graph = dict()
    graph["you"] = ["zhangsan", "lisi", "wangwu"]
    graph["zhangsan"] = ["xiaoming", "xiaohong"]
    graph["lisi"] = ["liniu", "you"]
    graph["wangwu"] = ["wangniu", "mango"]
    graph["xiaoming"] = []
    graph["xiaohong"] = []
    graph["liniu"] = []
    graph["wangniu"] = []
    graph["mango"] = []

    return graph


def check_person(person):
    """检查是否是销售商"""
    if person == 'mango':   # 给一个简单的条件，只要名字是mango的就是销售商
        return True
    return False


def search(name, graph):
    """广度优先搜索-销售商"""
    search_queue = deque()  # 创建队列
    search_queue += graph[name]  # 将一度关系加入队列

    searched = []  # 准备一个已经搜寻过销售商的列表

    # 只要队列不为空，
    while search_queue:
        person = search_queue.popleft()  # 取出第一个人

        # 判断该人是否已经检查过了
        if person not in searched:
            # 判断该数据是否是要搜索的销售商
            if check_person(person):
                print('%s is a mango seller' % person)
                return True

            else:
                # 不是，将这个人的朋友即二度关系加入队列
                search_queue += graph[person]

                # 将这个人标记为检查过
                searched.append(person)

    # 队列查完都没有就说明没找到
    return False


if __name__ == '__main__':
    graph = do_map()
    print(search('you', graph))