散列表相关的几个算法

根据算法图解一书写的两个算法：广度优先算法以及狄克斯特拉算法：

散列表

散列表在Python中也称作字典，通常的定义方式为： name = dict()

也可以写作： name = {}

散列表中的每一项都由Key(键)和Value(值)组成。散列表的搜寻效率在一般情况下接近O(1)而在最糟糕的情况下为O(n),可见是一个非常好的数据结构。

广度优先算法

广度优先算法顾名思义就是优先寻找临近的可能对象，当临近的对象均不是所搜寻的目标时，再去寻找较远的可能对象。

首先创建一张图，并填充对象：

下面是广度优先算法

graph = {}

graph["You"] = ["Mike", "Alice", "TankNee"]

graph["Mike"] = ["Dem", "Hans", "Chem"]

graph["Alice"] = ["Pigh"]

graph["TankNee"] = ["Chem"]

graph["Dem"] = []

graph["Hans"] = []

graph["Pigh"] = []

graph["Chem"] = []

其中的对应关系为：

{'Mike': ['Dem', 'Hans', 'Chem'],

'Pigh': [],

'Alice': ['Pigh'],

'TankNee': ['Chem'],

'Dem': [],

'Hans': [],

'You': ['Mike', 'Alice', 'TankNee'],

'Chem': []}

散列表是随机排布的，所以位置的前后并没有什么联系。并且其中的Key不仅仅可以对应一个值也可以对应一个列表。

我们接下来还需要一个队列来实现FIFO（First in First out）

queue = deque() # 生成一个队列

queue += graph["You"] # 将You对应的所有邻居都加入到队列里来

searched = [] # 一个列表，用来存放已经检查过的节点

count = 0 #一个计数器

接下来再去实现搜寻的函数

def personIsTrader(name):
    if(name[-1] == 'm'):
        return True
    else:
        return False
while(queue):
    people = queue.popleft() # 将队列最左边的值弹出，然后赋值给people
    if(people not in searched):
        if(personIsTrader(people)):
            print("He is Trader --"+people)
            print(count)
            count = 0
        else:
            queue += graph[people] # 如果这个额peop不是我们要搜寻的目标那么将他的邻居添加到队列的最后面
            count += 1
        # append 增加一个元素在列表的最末尾
        # 标记这个people已经完成检查
        searched.append(people)

狄克斯特拉算法

原理：找出图中开销最小的节点并且保证没有开销更小的方式到达该节点

下面是一个例子：

读者可以试着将这张加权图画出来

pic = {}
pic["Head"] = {}
pic["Head"]["A"] = 6
pic["Head"]["B"] = 2
pic["A"] = {}
pic["A"]["Tail"] = 1
pic["B"] = {}
pic["B"]["A"] = 3
pic["B"]["Tail"] = 5
pic["Tail"] = {}

# 下面是开销/权重表
# 记录当前到达这几个节点的最小开销
infinity = float("inf") # 无限大
costs = {}
costs["A"] = 6
costs["B"] = 2
costs["Tail"] = infinity
# 下面是父节点表
# 记录路的父节点
parents = {}
parents["A"] = "Head"
parents["B"] = "Head"
parents["Tail"] = None
# 记录已经检查过的节点
detected = []

# 搜寻距离最短的节点
def find_lowest_cost_node(cost):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in cost: # 遍历cost散列表
        cos = cost[node] # 把Key为node代表的值的Value传递给cos变量
        # 如果这个值比最小的值还要小并且这个节点没有被检查过那么就替换
        if cos <= lowest_cost and node not in detected:
            lowest_cost = cos
            lowest_cost_node = node
    # 将节点的键值作为返回值
    return lowest_cost_node

node = find_lowest_cost_node(costs)
print (costs)
while node is not None:
    cost = costs[node]
    neighbors = pic[node]
    for n in neighbors.keys():
        All_cost = cost + neighbors[n]
        if All_cost <= costs[n]:
            costs[n] = All_cost
            parents[n] = node
    detected.append(node)
    node = find_lowest_cost_node(costs)
print costs["Tail"]

适用范围：有向无环图用来寻找最小加权路