广度优先搜索算法，找出一个顶点到另外一个顶点需要最少经过的边数

#!python
#coding=utf-8

"""
广度优先搜索算法，
解决获取图中某点到某点最短路径问题：即从出发点到终点的边数最少)
时间复杂度O(V+E) V:图的顶点数 E:图的边数

假如有如下图所示：
郑州(ZZ)---------------广州(GZ)---深圳(SZ)
  |                       |          |
杭州(HZ)----北京(BJ)----天津(TJ)---武汉(WH)
  |            |                     |
  |---------重庆(CQ)------------------
从杭州到武汉有以下可选路径：
* 杭州-->郑州-->广州-->深圳-->武汉
* 杭州-->郑州-->广州-->天津-->武汉
* 杭州-->北京-->天津-->武汉
* 杭州-->重庆-->北京-->天津-->武汉
* 杭州-->重庆-->武汉
* 其他略
我们将通过广度优先搜索算法来找到【杭州-->重庆-->武汉】这条这段路径

@:param graph : 城市路线图
@:param start : 出发城市
@:param end   : 目的地城市
"""
def build_city_graph():
    # 元组数组，元组第一个属性为当前城市，第二个属性为当前城市的父级城市
    city_graph = {}
    city_graph["HZ"] = [("ZZ", "HZ"), ("BJ", "HZ"), ("CQ", "HZ")]
    city_graph["ZZ"] = [("GZ", "ZZ")]
    city_graph["BJ"] = [("TJ", "BJ"), ("CQ", "BJ")]
    city_graph["CQ"] = [("BJ", "CQ"), ("WH", "CQ")]
    city_graph["GZ"] = [("TJ", "GZ"), ("SZ", "GZ")]
    city_graph["TJ"] = [("GZ", "TJ"), ("WH", "TJ")]
    city_graph["SZ"] = [("WH", "SZ")]
    return city_graph


def bfs_path_search(graph, start, end):
	# 检索过的城市列表
    searched_cities = []
    # 待检索的城市路线队列
    city_queue = graph[start]
    found = False
    while city_queue:
    	# 每次循环都获取队列中的第一个城市
        current_city = city_queue.pop(0)
        if current_city not in searched_cities:
        	# 已经找到目的地
            if current_city[0] == end:
                found = True
                searched_cities.append(current_city)
                break
            else:
             	# 没找到目的地，将当前城市的子级城市加入待检索的城市队列
                city_queue += graph[current_city[0]]
                found = False
                searched_cities.append(current_city)
    path = []
    # 在已检索过的城市数据中找到已经搜索到的路径
    if found:
    	# 子找父，直到父亲节点为出发城市
        end_city = searched_cities.pop(-1)
        parent_city_name = end_city[1]
        path.append(end_city[0])
        while searched_cities:
            end_city = searched_cities.pop(-1)
            if end_city[0] == parent_city_name:
                parent_city_name = end_city[1]
                path.append(end_city[0])
            if end_city[1] == start:
                path.append(end_city[1])
                break
        path.reverse()
        join_str = "--->"
        print(join_str.join(path))
    else:
        print("not found from " + start + " to " + end + "path")


my_citys = build_city_graph()
# 找杭州到武汉的最短路径，即公交中的最少换乘概念
bfs_path_search(my_citys, "HZ", "WH")

执行结果：

HZ--->CQ--->WH