一、问题引入

假如我们所在的结点为v1，而我们需要到达v4结点，我们应该用什么方法？

 通过分析，我们发现不能从v1直接到达v4结点，因为没有v1为起点，指向v4的路径。那么我们能选择的路径似乎有这么几条：v1→v6→v4，v1→v2→v4，当然也有v1→v6→v2→v4这种路径，但这显然不是最优解。

 这个算法发现，前往以v1为起点前往v4结点至少需要三步。这种问题被称为最短路径问题（shorterst-path problem）。

 我们经常要找出最短路径的问题，这种问题可能是前往朋友家的最短路径，也可能是国际象棋中把对方将死的最少步数。解决最短路径问题的算法被称为广度优先搜索。

 我们要确定如何从v1结点前往v4结点，需要两个步骤：

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

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

二、图的介绍

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

 图用于模拟不同的东西是如何相连的。下面我们继续来看看广度优先搜索。

三、广度优先搜索

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

 第一类问题：从节点A出发，有前往节点B的路径吗？

 第二类问题：从节点A出发，前往节点B的哪条路径最短？

 前面我们计算从v1结点前往v4结点的最短路径时，使用过广度优先搜索。这个问题属于第二 类问题，即哪条路径最短？下面再来详细地研究这个算法，我们将使用它来回答第一类问题：有路径吗？

还是这张图，我们想知道：v6到v3结点有路径吗？首先在我们看来，一度关系胜过二度关系（即邻居关系胜过邻居的邻居），我们首先要找的是v6有没有直接到v3结点的路径。

 很遗憾，我们没有找到这种路径。于是我们便自然地想到二度关系，即看邻居的邻居有没有通往v3结点的路径，这里的二度关系胜过三度关系，以此类推。我们发现v6→v2→v3这条路径和v6→v4→v3这条路径了，在边无加权的情况下，这两条路径显然就是我们要找的最佳路径了！

 它当然优于其余的路径，比如v6→v2→v4→v3这条路径。

 因此，面对路径问题，你应先在一度关系中搜索，确定其中没有直达路径后，才在二度关系中搜索。

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

四、实现图

 首先，需要使用代码来实现图。图由多个节点组成。

 每个节点都与邻近节点相连，如果表示类似于“v1→v2” 这样的关系呢？我们知道的一种结构让你能够表示这种关系，它就是散列表！散列表让你能够将键映射到值。在这里，我们要做的只是将节点映射到其所有邻居。

 表示这种映射关系的Python代码如下：

graph = {} 
graph["v1"] = ["v2", "v6"] 

我们需要注意：“v1”被映射到了一个数组，因此graph[“v1”]是一个数组，其中包含了“v1”的所有邻居。 图不过是一系列的节点和边，因此在Python中，只需使用上述代码就可表示一个图。

graph = {} 
graph["v1"] = ["v2", "v6"] 
graph["v2"] = ["v3", "v4"] 
graph["v3"] = [] 
graph["v4"] = ["v1", "v3","v5"] 
graph["v5"] = [] 
graph["v6"] = ["v2"]

如此，便能实现以上图。

#键—值对的添加顺序并不重要，换言之，如果你这样编写代码：
graph["v2"] = ["v4","v3"] 
graph["v1"] = ["v6","v2"] 
#而不是这样编写代码：
graph["v1"] = ["v2","v6"] 
graph["v2"] = ["v3","v4"] 
#其对结果无影响
#散列表是无序的，因此添加键—值对的顺序无关紧要。

五、实现算法

 这种算法的工作原理如下：

1、创建一个队列，用于检查要检查的结点

2、从队列中弹出一个结点

3、检查这个结点是不是原结点的邻居

 a）是，则找到目标路径

 b）否，则将这个结点的所有邻居都假如队列

4、回到第2步

5、如果队列为空，就说明原结点的没有到目标结点的路径

from collections import deque 
search_queue = deque()      #创建一个队列
search_queue += graph["v1"] #将你的邻居都加入到这个搜索队列中

while search_queue:         #只要队列不为空，
  person = search_queue.popleft() #就取出其中的第一个结点
  if person_is_target(person):  #检查这个人是否是目标结点
    print person + " is the target!"  #是目标结点
    return True 
  else: 
    search_queue += graph[node]#不是目标节点，将它的邻居都加入到这个搜索队列中
return False #如果到达了这里，就说明队列中没有到目标节点的路径

最后，你还需编写函数person_is_target，判断一个结点是不是目标节点，如下所示：

def person_is_taregt(node): 
  return node

这个算法将不断执行，直到满足以下条件之一：

    找到目标节点；

    队列变成空的，这意味着原结点没有到目标结点的路径。

  具体实现算法如下：

def search(node): 
  search_queue = deque() 
  search_queue += graph[node] 
  searched = []               #这个数组用于记录检查过的结点
  while search_queue: 
    person = search_queue.popleft() 
    if not person in searched:        #仅当这个结点没检查过时才检查
      if person_is_target(person): 
        print person + " is the target!" 
        return True 
      else: 
        search_queue += graph[[person] 
        searched.append(person)   #将这个结点标记为检查过
  return False 
search("v1") 

六、运行时间

 如果你在你的整个图网中搜索目标节点，就意味着你将沿每条边前行（边是从一个结点到另一个结点的箭头或连接），因此运行时间至少为O(边数)。

 我们还使用了一个队列，其中包含要检查的每个结点。将一个结点添加到队列需要的时间是固定的，即为O(1)，因此对每个人都这样做需要的总时间为O(结点数)。所以，广度优先搜索的运行时间为O(人数 + 边数)，这通常写作O(V + E)，其中V为顶点（vertice）数，E为边数。

未完待续