邻接表

摘要: 邻接表的应用：桶、开散列表、树和图的存储

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们总结一下邻接表的各种应用。包括桶、开散列表、树和图的存储。

$0 邻接表

邻接表可以看成带有索引数组的多个数据链表。索引数组称为表头数组，其中每一项指向一个数据链表的表头。

邻接表中的数据天然地被分为若干类，每一类的数据在一个链表中。

这里的表头数组和数据链表均可以根据插入删除以及查询的需要选择用动态数组或链表实现。

邻接表的应用

许多数据结构用到了邻接表的这种将数据分类的特性：桶、开散列表、树和图的存储是比较重要的三个应用。

---

$1 桶

链表+链表+哈希索引的桶结构设计

• 桶节点，数据节点均由链表维护。支持快速插入删除。
• 哈希索引将 key 映射到两个指针，一个指向桶节点，另一个指向数据节点。支持快速查询。

list<Bucket> buckets;
unordered_map<string, Index> mapping;

struct Bucket
{
    int val;
    list<string> keys;
    Bucket(int val):val(val)
    {
        keys = list<string>();
    }
};

struct Index
{
    list<Bucket>::iterator bucket_it;
    list<string>::iterator key_it;
    Index(list<Bucket>::iterator bucket_it, list<string>::iterator key_it):bucket_it(bucket_it),key_it(key_it){}
    Index(){}
};

895. 最大频率栈

题解参考：【设计难题】力扣895-最大频率栈

460. LFU缓存

题解参考：力扣460-LFU

432. 全 O(1) 的数据结构

题解参考：【设计难题】力扣432-全O(1)的数据结构

---

$2 开散列表

• 表头数组用数组实现。没有插入删除操作，支持快速查询(随机访问)。
• 数据链表用链表实现。支持快速插入删除，链表比较长的时候查询性能弱。

using PII = pair<int, int>; // key -> val
vector<list<PII>> vec;

706. 设计哈希映射

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类：

• MyHashMap() 用空映射初始化对象
• void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
• int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
• void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

示例：
输入：
[“MyHashMap”, “put”, “put”, “get”, “get”, “put”, “get”, “remove”, “get”]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
输出：
[null, null, null, 1, -1, null, 1, null, -1]
解释：
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1); // 返回 1 ，myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3); // 返回 -1（未找到），myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值）
myHashMap.get(2); // 返回 1 ，myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 [[1,1]]
myHashMap.get(2); // 返回 -1（未找到），myHashMap 现在为 [[1,1]]

提示：

0 <= key, value <= 1e6
最多调用 1e4 次 put、get 和 remove 方法

代码 (C++)

class MyHashMap {
public:
    /** Initialize your data structure here. */
    MyHashMap() {
        vec = vector<list<PII>>(N);
    }

    /** value will always be non-negative. */
    void put(int key, int value) {
        int pos = hash(key);
        list<PII>::iterator iter = vec[pos].begin();
        while(iter != vec[pos].end() && iter -> first != key)
            ++iter;
        if(iter == vec[pos].end())
            vec[pos].push_front(PII(key, value));
        else
            iter -> second = value;
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        int pos = hash(key);
        list<PII>::iterator iter = vec[pos].begin();
        while(iter != vec[pos].end() && iter -> first != key)
            ++iter;
        if(iter == vec[pos].end())
            return -1;
        return iter -> second;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        int pos = hash(key);
        list<PII>::iterator iter = vec[pos].begin();
        while(iter != vec[pos].end() && iter -> first != key)
            ++iter;
        if(iter != vec[pos].end())
            vec[pos].erase(iter);
    }

private:
    const int N = 20011;
    using PII = pair<int, int>;
    vector<list<PII>> vec;

    int hash(int x)
    {
        return x % N;
    }
};

$3 树和图

邻接表

• 表头数组 g 用数组实现。没有插入删除操作，支持快速查询(随机访问)。
• 数据链表用动态数组(vector)实现。支持快速插入删除(在尾部操作)，不支持查询。

using PII = pair<int, int>; // 带边权

vector<vector<PII>> g;

void add_edge(int u, int v, int w)
{
    g2[u].emplace_back(v, w);
    g2[v].emplace_back(u, w);
}

链式前向星

在建图的邻接表的基础上，表头数组不变，数据链表改为用链表实现，每次插入均采用头插。

这里的链表用的是一种比较抽象的实现方式。

用一个数组 vector<Edge> edges 维护所有边。head[u] 指向 edges 的某个下标，表示数据链表的起点。

Edge 中有一个 next 字段，指向 edges 中的某个下标表示同起点的上一条边，实现逻辑上的单链表。head[u] 始终是从 u 连接出的上一条边。

struct Edge
{
    int v, int w;
    int next; // 同起点的上一条边的编号
    Edge(int v, int w, int next):v(v),w(w),next(next){}
};

vector<Edge> edges;
vector<int> head;

void add_edge(int u, int v, int w)
{
    edges.emplace_back(v, w, head[u]);
    head[u] = edges.size() - 1;
    edges.emplace_back(u, w, head[v]);
    head[v] = edges.size() - 1;
    // 如果是无向图，插量词, 此时 e -> e^1 (e的反向边是 e^1) 这是一个好特性
}

---