《图解算法》系列学习（二）

散列表

最有用的基本数据结构之一。查找时间都为O(1)，O(1)被称为常量时间，即所需的时间都相同。

散列函数将输入映射到数字。它需要满足下列几个条件：

1）他必须是一致的，即你不管什么时候每次输入相同时，输出都要一样。如果不是这样，散列表将毫无用处。

2）它应将不同的输入映射到不同的数字。

散列表在Python语言中时用字典dict{}来表示。

冲突

有可能不同的输入会映射到同一个位置，这就叫冲突。因此可以在同一个位置储存一个链表，这样才不会发生冲突。解决冲突的方法：

1）散列函数很重要。理想的散列函数将键均匀的映射到散列表的不同位置。

2）散列函数用的好，链表就不会很长。

性能

散列表的查找速度与数组一样快，而插入与删除速度与链表一样快，因此它兼具两者的优点。而要避免冲突，需要有：

1)较低的填装因子；2)良好的散列函数

填装因子=散列表包含的元素数/位置总数。

填装因子越低，发生冲突的可能性越小，散列表的性能越高。一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。

广度优先搜索算法

广度优先算法能让你找出两样东西之间最短的距离。使用广度优先搜索可以：

1）编写国际跳棋A，计算最少走多少步就可以获胜

2）编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词

3）根据你的人际关系网络找到关系最近的医生

图算法是广度优先算法最有用的

图由节点和边组成。一个节点可能与众多节点直接相连，这些节点被称为邻居。广度优先搜索是一种用于图的查找算法，可帮助回答两类问题：

第一类：从节点a出发，有前往b的路径吗

第二类：从节点a出发，前往节点b的哪条路径最短

队列是一种先进先出（First In First Out FIFO）的数据结构，可用于广度优先搜索算法。

实现图的算法是由散列表表示

有向图用箭头表示，关系是单向的，无向图没有箭头，直接相连的节点叫做邻居。例如下面的两个图是等价的。

实现算法

from collections import deque
 
graph={}
graph["you"]=["alice","Bob","claire"]    #我的一度关系
 
def person_is_seller(name):     #判断是否是销售的
    return name[-1]=='m'      #名字末尾为m说明是销售的
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 a mango seller!')
                return True
            else:
                search_queue+=graph[person]  #表示销售商就将这个人的朋                                                           友都加入搜索队列
                searched.append(person)  #将这个人标记为检查过
    return False   #如果达到这里就说明队列中没有人是销售商
 
search("you")

算法执行过程如下图

运行时间

如果在你的整个人际网络中搜索销售商，就意味着你将沿着每条边前行（边是从一个人到另外一个人的箭头或连接），因此运行时间至少为O（边数）。

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

有序列表中，如果任务A依赖于任务B，在列表中任务A就必须在任务B后面，这种被称为拓扑排序，使用它可以根据图创建一个有序列表。如下图就是拓扑顺序。

下面的图被称为树。树是一种特殊的图，其中没有往后指的边