邻接表表示法的空间复杂度为何是O(V+E)而非O(E)

参考实现代码 #

#include<bits/stdc++.h>
using namespace std;
const int N=1e3;
vector <int> graph2[N];
int main(){
    int n,m;
    cin>> n>>m;
    for(int i=0;i<m;i++){
        int v1,v2;
        cin>>v1>>v2;
        graph2[v1].push_back(v2);
        graph2[v2].push_back(v1);
    }
    for(int i=1;i<=6;i++){
        for(int j=0;j<graph2[i].size();j++){
            cout<<graph2[i][j]<<" ";
        }
        cout<<endl;
    }
}

测试输入输出 #

输入 #

6 9
1 3
1 5
3 5
3 4
3 6
3 2
2 6
4 6
5 6

输出 #

3 5 
3 6 
1 5 4 6 2 
3 6 
1 3 6 
3 2 4 5 

核心疑问 #

实现中使用数组下标直接对应顶点编号，仅在vector中存储边关联的邻接节点，认为顶点编号作为索引默认存在，没有额外占用边的存储空间，因此不理解邻接表空间复杂度为O(V+E)而非O(E)的原因。

具体原因 #

• 你认为“顶点作为数组索引不占空间”是认知偏差：代码中定义的vector<int> graph2[N]是长度固定为N的数组，数组每个位置存储的都是一个独立的vector实例。哪怕某个顶点是孤立点、对应的vector里没有存任何邻接节点，这个空vector对象本身依然要占用固定内存，这部分内存总量和顶点数量V线性相关，和边数E没有关系。
• 空间复杂度统计的是数据结构整体的全部内存开销，不是只统计存储边内容的部分。举个极端场景：如果一张图有1000个顶点，但一条边都没有（E=0），你依然要开辟长度为1000的数组来存储每个顶点对应的邻接表入口，这部分开销显然不属于存储边的范畴，不可能被归入O(E)的统计范围。
• 所有邻接表实现都绕不开顶点对应的入口开销：不管是用数组存邻接链表头节点，还是用哈希表建立顶点到邻接表的映射，都必须为每个顶点分配存储邻接表入口的空间，这部分开销量级为O(V)；加上存储所有邻接关系的边开销（无向图为O(2E)、有向图为O(E)），总空间复杂度就是O(V+E)。
• 你这次测试用例里的6个顶点全部有相连的边，所以感知不到孤立顶点对应的固定空间开销，才会误以为只有存储边的空间占用。

内容的提问来源于stack exchange，提问作者Reason Behind Tech