跳到主要内容

六.图的基本操作

0.图的基本操作动态演示​

图的操作效率很大程度上取决于存储结构。 下方对比了邻接矩阵和邻接表在"添加边"和"删除顶点"时的不同表现。

考研重点
  • 邻接矩阵：删点极慢 O(|V|²)，因为要搬移大量数组元素。加边极快 O(1)。
  • 邻接表：删点较慢 O(|E|)，因为要遍历所有边表找入边。加边极快 O(1) (头插法)。
Step 1/4初始状态：A-B, B-C。现在我们要添加边 (A, D)。
1// 邻接矩阵添加边 (x, y)
2void AddEdge(int x, int y) {
3    // 1. 检查边是否已存在
4    if (Edge[x][y] == 1) return;
5    
6    // 2. 标记对应格子为 1
7    Edge[x][y] = 1;
8    // 无向图还需要标记对称点
9    Edge[y][x] = 1; 
10}
A
B
C
D
A
0
1
0
0
B
1
0
1
0
C
0
1
0
0
D
0
0
0
0
Adjacency Matrix [ 4 x 4 ]

1. Adjacent(G,x,y) —— “有没有这条边？”​

  • 语义

    无向图问 (x,y) 是否存在；有向图问 <x,y> 是否存在。

  • 邻接矩阵

    直接看 matrix[x][y] 是 0 还是 1。

    Θ(1) —— 一次随机访问。

  • 邻接表

    沿 x 的出边链表扫到 y 为止。

    最坏 Θ(deg(x))，稀疏图常称 O(1)O(|V|)。

2. Neighbors(G,x) —— “把 x 的所有邻居一次性列出来”​

  • 矩阵

    扫整行 matrix[x][0 … |V|−1]，收集为 1 的下标。

    Θ(|V|) 躲不掉，即使稀疏。

  • 表

    把 x 的出边链表从头到尾走一遍即可。

    Θ(deg(x)) 即 O(1)O(|V|)。

3. InsertVertex(G,x) —— “加一个新顶点”​

  • 矩阵

    扩容二维数组（或重新分配），把新行/列填 0。

    理论 Θ(|V|²)，但考研层面通常认为 Θ(1)（“摊销”或预先留好）。

  • 表

    在顶点数组末尾追加一个空头结点。

    纯 Θ(1)。

4. DeleteVertex(G,x) —— “把顶点 x 及其所有边抹掉”​

  • 矩阵

    把第 x 行和第 x 列清 0，再把最后一行/列搬过来（若要求连续下标）。

    Θ(|V|)。

  • 表（重点）

    1. 删 x 的出边：Θ(deg(x))。
    2. 删指向 x 的入边：必须遍历所有顶点的出边链表，遇到指向 x 的结点就摘除。

    总代价 Θ(|V|+|E|)（无向图同理，每条边会出现两次）。

    这是邻接表最昂贵的操作之一。

5. AddEdge(G,x,y) —— “加一条新边”​

  • 矩阵

    matrix[x][y] = 1（无向再加 matrix[y][x]）。

    Θ(1)。

  • 表

    头插法把 y 结点挂到 x 链表；无向图再反向插一次。

    Θ(1)。

6. RemoveEdge(G,x,y) —— “删边”​

  • 矩阵

    置 0 即可，Θ(1)。

  • 表

    在 x 的出边链表中找到并摘掉 y 结点；无向图再反向做一次。

    Θ(deg(x))（最坏 O(|V|)）。

7. FirstNeighbor(G,x) / NextNeighbor(G,x,y)​

  • 两个操作连用可迭代访问 x 的全部邻居，无需一次性列出。

  • 矩阵

    顺序扫行，第一个非 0 即返回；下一条继续往后扫。

    每次 Θ(1)Θ(|V|)（看稀疏程度）。

  • 表

    直接返回头结点；Next 就是链表指针后移。

    Θ(1) 每次。

8. Get_edge_value / Set_edge_value​

  • 矩阵随机访问 Θ(1)。
  • 表需沿 x 链表找到 y 再读/写，Θ(deg(x))。

9. 入度专用细节（有向图）​

邻接表没有逆表时：

  • 求入度、删入边、列前驱，都不得不扫全部边 Θ(|E|)。
  • 若额外维护“逆邻接表”，可把入度操作也降到 Θ(deg_in(x))。

10. 一句话口诀（记忆版）​

矩阵恒定行列查，代价总与 |V| 齐；表按度数走链表，删顶点要扫全图，入度无逆表就悲剧。

💬 留下你的问题或见解