📢📢📢📣📣📣
🌻🌻🌻Hello，大家好我叫是Dream呀，一个有趣的Python博主，小白一枚，多多关照😜😜😜
🏅🏅🏅CSDN Python领域新星创作者，大二在读，欢迎大家找我合作学习
💕入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！🚀🚀🚀
💓最后，愿我们都能在看不到的地方闪闪发光，一起加油进步🍺🍺🍺
🍉🍉🍉“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~🌈🌈🌈
🌟🌟🌟✨✨✨

@TOC

6.1图简介

图算法：广度优先搜索！
前往某一地点，需要的最短路径被称为是：最短路径问题
解决最短路径问题的算法被称作：广度优先搜索

6.2图是什么

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

6.3广度优先搜索

广度优先搜索是一种用于图的查找算法，可帮助回答两类问题：
第一类问题：从节点A出发，有前往B节点的路径吗？
第二类问题：从节点A出发，前往节点B的哪条路径最短呢？
拿卖水果的例子来说，如果你的朋友不是经销商的话，就将你的朋友也加入到名单中。这意味着你将在她的朋友、朋友的朋友等中查找。使用这种算法将搜遍你的整个人际关系网，知道找到水果经销商。这就是广度优先搜索算法。

6.3.1查找最短路径

首先，拿上文来说，你应该先在一度关系中搜索，确定其没有芒果销售商后，才在二度关系中搜索。
有一个可实现这种目的的数据结构，那就是队列。

6.3.2队列

队列的工作原理和现实生活中的队列完全相同。如果你排在他前面，你将先上车。队列类似于栈，你不能随机地访问队列的元素。
队列只支持两种操作：入队和出队
队列先进先出，而栈后进先出！

6.4实现图

图由多个节点组成，每个节点都与邻近节点相连。
散列表让你能够将键映射到值，在这里只需要将节点映射到其所有邻居。散列表是无序的，因此添加键值对的顺序无关紧要！
关系单向：有向图
无向图没有箭头，直接相连的节点互为邻居。

6.5实现算法

首先，创建一个队列。在Python中，可使用函数deque来创建一个双端队列。

from collections import deque
search_queue=deque()
search_queue+=graph["you"]

别忘了，这里的graph[‘you’]是一个数组，其中包含了你的所有邻居，如[‘alice’,‘bob’,‘claire’]。这些邻居都将加入到搜索队列里。

while search_queue:
    person=search_queue.popleft()
    if person_is_seller(person):
        print(person + 'is seller')
        return True
    else:
        search_queue+=graph[person]
return False

最后你还需要编写函数来判断一个人是不是经销商，如下所示：

    def person_is_seller(name):
        return name[-1]=='m'

检测这个人的名字是否以m结尾：如果是，他就是经销商。这种方法有点搞笑，但就这个实例而言是可行的。
这个算法将不断执行，直到满足以下条件之一：
1.找到一位经销商
2.队列为空，这将意味着你的人际关系网中没有经销商。

A既是B的朋友，又是C的朋友，因此他会两次被加入到队列中，这就会导致后手检测的将变成无用功。

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

6.5.1运行时间

如果你的整个人际关系网中搜索芒果销售商，就意味着你将沿着每条边前行，因此运行时间至少O（边数）
你还使用了一个队列，其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的，即为O（1），因此对每个人都这样做需要的总时间为O（人数）。所以，广度优先搜索的运行时间为O（人数加边数），通常记作O（V+E），其中V为顶点数，E为边数。

6.5.2树

有一种图由节点和边组成，但没有往上指的箭头，这种图被称为树，树是一种特殊的图！

6.6小结

1.广度优先搜索指出是否有从A到B的路径；
2.如果有，广度优先搜索将找出最短路径；
3.面临类似于寻找最短路径的问题时，可以尝试使用图来建立模型，再使用广度优先搜索来解决问题；
4.有向图的边为箭头，箭头的方向指定了关系的方向；
5.无向图的边不带箭头，其中关系是双向的。
6.队列是先进先出的；
7.栈是后进先出的
8.你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。
9.对于检查过的人，务必不要再去检查，否则可能导致无限循环。

好啦，这就是今天要给大家分享的全部内容了
如果你喜欢的话，就不要吝惜你的一键三连了~