算法图解阅读笔记——第三曲（散列表和广度优先搜索）

小灰灰 2021-05-12 11:50 409阅读 0赞

#### 目录结构 ####

第5章 散列表

第6章 广度优先搜索

--------------------

#### 正文 ####

## 散列表 ##

*  散列表也称为**散列映射**、**映射**、**字典**、**关联数组**。在python中以字典的形式实现

### 散列函数：将输入映射到数字 ###

*  散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字。
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center]
 *  散列函数两个要求：
    
    1.  散列函数总是将同样的输入映射到相同的索引（在相同输入的情况下，输出必须一致）
    2.  散列函数将不同的输入映射到不同的索引（在不同输入的情况下，输出也必须不同）

### 散列表应用案例 ###

*  **散列表用于查找**
    
    1.  如存一个key为联系人，value为联系电话的散列表（即联系人映射到联系电话），这样便可非常快速的进行查找。
    2.  再如存一个key为网址，value为IP的散列表（即网址映射到IP），这样的过程叫做DNS解析。
 *  **防止去重**
    
    1.  如大选要到了，每个公民需要进行投票，且只能投一次，可以创建一个散列表将投过票的公民记录在key中，避免重复，防止二次投票。
 *  **将散列表用于缓存**
    
    1.  为了避免服务器重复计算可以使用缓存机制：让网站将数据记住。那么可以使用散列表实现。在key中存储需要缓存的网站，在value中存储该网站中需要缓存的数据。

### 散列表的冲突 ###

*  加入某个键已经有对应的值了，现在又有一个值对应到了这个键上，这就引起会**冲突**
 *  散列表**其实并不总是将不同的键映射到数组的不同位置**，所以一个好的散列函数很重要，散列函数可以将键均匀地映射到列表的不同位置。

### 散列表的性能 ###

*  散列表在平均情况下查找、插入、删除的操作时间都是 O ( 1 ) O(1) O(1)
 *   O ( 1 ) O(1) O(1)被称为**常量时间**，并不意味着马上，而是说不管散列表多大，所需时间都相同。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 1]

## 广度优先搜索 ##

### 什么是图 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 2]

*  图是由节点和边组成的。如上图（`ALEX`和`RAMA`是两个节点，他们之间的连线为边）

### 有向图和无向图 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 3]

*  有向图中有箭头指向，对于上图有向图中的两个节点来说，`ROSS`指向`RACHEL`的箭头①仅仅表示`ROSS`有`RACHEL`的联系方式，而`RACHEL`指向`ROss`的箭头②才表示`RACHEL`也有`ROss`的联系方式。
 *  无向图中的关系③则表示两个节点的关系是互相的，如`ROSS`的另一半是`RACHEL`，`RACHEL`的另一半是`ROSS`。
 *  **注意**：部分算法仅支持有向图，而部分算法仅支持无向图。

### 什么是广度优先搜索 ###

*  广度优先搜索是一种用于图的查找算法，可解决两类问题：
    
     *  第一类问题：从节点A出发，有前往节点B的路径吗？
     *  第二类问题：从节点A出发，前往节点B的哪条路径最短？
 *  面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来  
    解决问题。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 4]

*  从上述两类问题着手，以书本中的找芒果商为例，因为要找的是最短路径，广度优先搜索先查找一度关系（你的朋友）中是否有芒果商，再查找二度关系（你朋友的朋友），那么最先找到的芒果商就是最近的。

### 广度优先搜索的实现 ###

*  因为要先找一度关系，再找二度关系，就需要按顺序添加一度关系和二度关系，并按顺序取出。正好符合数据结构中队列的规则。
    
     *  **队列**：就和我们排队一样，它是一种先进先出（First In First Out，FIFO）的数据结构
        
         *  支持操作：**入队**（从队尾入）和**出队**（从队头出）
            
            ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 5]

**实现**：

from collections import deque
    
    
    def person_is_seller(name):
        return name[-1] == "m"
    
    graph = { }   # 创建图
    graph['you'] = ['alice', 'bob', 'claire']
    graph['alice'] = ['peggy']
    graph['bob'] = ['anuj', 'peggy']
    graph['claire'] = ['thom', 'jonny']
    graph['anuj'] = []
    graph['peggy'] = []
    graph['thom'] = []
    graph['jonny'] = []
    
    search_queue = deque()   # 创建队列
    search_queue += graph['you']
    is_exit = False
    searched_person = []   # 为了避免重复判断，导致无限循环
    
    while search_queue:
        person = search_queue.popleft()
        if person in searched_person:
            continue
    
        if person_is_seller(person):
            print(person + 'is a mango seller!')
            is_exit = True
            break
        else:
            search_queue += graph[person]
            searched_person.append(person)
    print(is_exit)
    
    # Out
    # thomis a mango seller!
    # True

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20210511/4e3b9b5df9eb453384f353d378fd0eec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210511/6e4ee4cd9fb7499296cec0b1006e7d64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210511/bec7a0eacd9f40f4b6f6733eef448523.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20210511/8a425272be244a959adfeca396b46b99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20210511/8cde263602384f998334d7f8efd67dd3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20210511/3c34b990a60541d1b7f0018f2f26f187.png