邻接表

裘天瑞

2024-11-09 18:47:33

发布于：浙江

4阅读

0回复

0点赞

邻接表

定义

邻接矩阵一定需要去开辟 $n \times n$ 的空间，当一个题目的顶点数量 $n > 10^5$ 在一个数组当中是无法开辟这么大的空间的。因此，我们需要使用邻接表来存储图的结构。

邻接表的优势

空间复杂度：对于一个有 $n$ 个顶点的图， $m$ 条边的一张图，邻接表只需要 $O(n+m)$ 的空间，其中 $m$ 是边的数量。
插入和删除操作：对于邻接表来说，插入和删除操作的时间复杂度都是 $O(1)$ 。
稀疏图：对于一个稀疏图来说，邻接表的存储空间可以大大减少。

邻接表的实现

邻接表相当于是 $n$ 条链表的集合，每个链表存储了与某个顶点相连接的其他顶点。

比如，链表数组的名称为 $mp$ ，对于顶点 $v$ ， $mp[v]$ 指向一个链表，链表中存储了与 $v$ 相连接的其他顶点。

假如与点 $v$ 相连接的顶点有 $1,2,3$ ,那么 $mp[v]$ 中存储的就是 $1,2,3$ 。

如果需要储存权值，只需要将链表当中的每一个空间划分为两个部分，第一个部分存储顶点，第二个部分存储权值。

使用指针来去实现链表，构成一个邻接表。动态链表的实现，删除和插入的操作都为O(1)。
使用vector来代表其中的链表，构成一个邻接表。静态链表，删除操作为O(n)，插入操作为O(1)。

// vecotr静态链表实现邻接表
struct Edge {
    int v;
    int w;
};
vecotr<Edge> mp[MAXN]; // 邻接表
mp[v].push_back(Edge{u, w}); // 插入边

// 动态链表实现邻接表
struct Node {
    int v;
    int w;
    Node* next;
};
Node* mp[MAXN]; // 邻接表
Node* head[MAXN]; // 头指针
int cnt[MAXN]; // 记录每个顶点的度

void addEdge(int u, int v, int w) {
    Node* node = new Node{v, w, head[u]};
    head[u] = node;
    cnt[u]++;
}
void delEdge(int u, int v) {
    Node* p = head[u];
    Node* pre = nullptr;
    while (p) {
        if (p->v == v) {
            if (pre) {
                pre->next = p->next;
            } else {
                head[u] = p->next;
            }
            delete p;
            cnt[u]--;
            return;
        }
        pre = p;
        p = p->next;
    }
}

有帮助，赞一个

去预览

0/2000

这里空空如也

邻接表

定义

邻接表的优势

邻接表的实现

热门讨论