图解算法学习笔记（六）：广度优先搜索

本章内容;

•        学习使用新的数据结构图来建立网络模型；
•        学习广度优先搜索；
•        学习有向图和无向图；
•        学习拓扑排序，这种排序算法指出了节点之间的依赖关系。

1）图简介

假设你住在旧金山，要从双子峰前往金门大桥。你想乘公交车前往，并希望换乘最少。可乘坐的公交车如下：

从图中我们可以发现，前往进门大桥的最短路径需要三步，这种问题被称为最短路径问题(shorterst-path problem)。

要确定如何从双子峰前往金门大桥，需要两个步骤：

• 使用图来建立问题模型。

• 使用广度优先搜索解决问题。

2）图是什么

图模拟一组连接，图由节点(node)和边(edge)组成。

3）广度优先搜索

广度优先搜索是一种用于图的查找算法。可回答两类问题：

从A节点有前往几点B的路径吗？哪条路径最短？

下面来看一个例子：假设你经营这一个芒果农场，需要寻找芒果经销商，以便将芒果卖给他。为此，你可在朋友中查找。

这种查找很简单，首先创建一个朋友名单。然后依次检查名单中的每个人，看看他是否是芒果销售商。

假设你没有朋友是芒果销售商，那么你必须在朋友的朋友中查找。

检查名单中的每个人时，你都将其朋友加入名单。

1.查找最短路径

人物关系如图所示：

在你看来，一度关系胜过二度关系，二度关系胜过三度关系，等等。因此，你应现在一度关系中搜索，确定其中没有芒果销售商后，才在二度关系中搜索。广度优先搜索就是这样做的！

2.队列

队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队，如果你排在他前面，你讲先上车。队列只有两种操作：入队和出队。

队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out, LIFO）的数据结构。

4）实现图

使用散列表，表示节点与节点之间的关系！

有向图与无向图关系如图：

5）实现算法

概述一下算法原理：

寻找芒果销售商的Python源码为：

#从标准库导入队列元素
from collections import deque

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

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]
    # This array is how you keep track of which people you've searched before.
    searched = []
    while search_queue:
		#队首元素出队
        person = search_queue.popleft()
        # Only search this person if you haven't already searched them.
        if not person in searched:
            if person_is_seller(person):
                print person + " is a mango seller!"
                return True
            else:
                search_queue += graph[person]
                # Marks this person as searched
                searched.append(person)
    return False

search("you")

6）小结

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