图的邻接表表示的基本原理
数据结构的核心组成
在图的邻接表实现中，核心数据结构包括一个用于存放每个顶点邻接边的边链表头指针数组，以及用于存放边信息的边结点。通过为每个顶点维护一个指向其邻接边的链表的头结点，可以实现对图的高效存储与遍历。
具体来说，边结点通常包含一个 目标顶点字段和一个指向下一条边的 next 指针，还可以额外保存边权等信息。这样设计的好处是：边的数量随图的规模线性增长，并且在进行顶点遍历时可以逐一访问该顶点的所有邻接边。
时间与空间复杂度
与稀疏图的邻接表相比，空间复杂度为 O(V+E)，远优于使用完整矩阵的 O(V^2)。对于遍历某个顶点的邻接边，时间复杂度为 O(deg(u))，整张图的遍历时间为 O(V+E)。
通过使用链表结构，邻接表在边的插入与扩容方面具有较高的灵活性，尤其在图的规模动态变化时，能保持较低的额外开销。边的数量 E 与顶点数量 V 的增长直接影响总体的空间与时间表现。
C++实现：数据结构设计
顶点和边的结构
实现通常定义一个 Edge 结构，包含目标顶点 to、下一条边的指针下标 next，以及可选的边权 w。结合一个 head 数组来记录每个顶点的第一条边的下标，从而实现邻接表的存储。
该设计的关键点在于：通过一个数组或向量保存所有边节点，并利用 头指针数组 head 维护每个顶点的边链表起始位置，便于快速按顶点遍历其相邻边。
邻接表的存储结构
在 C++ 中，可以使用 std::vector 来存放边节点，利用一个整型下标作为 边在数组中的位置，再通过 next 指针实现链表连接，从而实现动态扩容的邻接表。
这种实现方式兼具简单性和性能，适合教学与实际应用中的混合场景，能够清晰地表达 关系型存储 与 遍历算法 的紧密关系。
添加边与图的构造
添加边时，可以采用“头部插入”的方式把新的边结点放到该顶点的链表头部，这样的时间复杂度为 O(1)；图的构造则是对每条边执行一次边节点的创建与连接操作，整体空间开销与边数线性相关。
完整代码示例：构建无向图的邻接表
代码概览与核心函数
下面给出一个完整的 C++ 示例，展示如何使用邻接表实现一个无向图的存储、边添加以及简单的遍历（BFS）功能。核心函数包括 addEdge、addUndirected、以及 bfs 的实现，体现了邻接表在边的存取和遍历方面的优势。
// C++ adjacency list using vectors with edge struct
#include <bits/stdc++.h>
using namespace std;struct Graph {struct Edge { int to; int next; int w; };int n;vector head;vector edges;Graph(int n=0): n(n) { head.assign(n, -1); }void init(int _n) { n = _n; head.assign(n, -1); edges.clear(); }void addEdge(int u, int v, int w=0) {Edge e{v, head[u], w};edges.push_back(e);head[u] = (int)edges.size()-1;}void addUndirected(int u, int v, int w=0){addEdge(u,v,w);addEdge(v,u,w);}// BFSvector bfs(int s){vector dist(n, -1);queue q;dist[s] = 0; q.push(s);while(!q.empty()){int u = q.front(); q.pop();for(int i=head[u]; i!=-1; i=edges[i].next){int v = edges[i].to;if(dist[v] == -1){dist[v] = dist[u] + 1;q.push(v);}}}return dist;}
};
int main(){Graph g(5);g.init(5);g.addUndirected(0,1);g.addUndirected(0,2);g.addUndirected(1,2);g.addUndirected(1,3);g.addUndirected(3,4);auto dist = g.bfs(0);for(size_t i=0;i<dist.size();++i) {cout << i << \": \" << dist[i] << endl;}return 0;
}
运行示例与说明
运行上述程序时，将从顶点 0 出发进行广度优先遍历，输出各顶点到起始点的距离，例如 0 的距离为 0，其他顶点的距离依次更新。此示例直观地展示了 邻接表的遍历性，以及如何在 C++ 中构建并使用无向图的边链表。
原理解析：遍历、操作与复杂度分析
遍历与搜索算法
在邻接表实现中，遍历一个顶点的所有邻接边通常需要遍历其链表中的所有边结点，因此在广度优先搜索（BFS）或深度优先搜索（DFS）中，外层对顶点集合的遍历与内层对链表的遍历共同构成时间复杂度。
具体而言，整图的遍历时间复杂度为 O(V+E)，其中 V 是顶点数量，E 是边的数量；空间复杂度主要来自 头指针数组 与 边结点数组，与边数线性相关。
插入和删除边的复杂度
插入边在邻接表中通常为 O(1)，因为新边可以直接插入到头部的链表中。删除边则需要定位并移除目标边结点，若以链表方式实现，平均需要遍历该顶点的邻接链表，复杂度为 O(deg(u))；若要全图删除任意一条边，最坏情况下为 O(E)。实际实现中，删除常通过标记位等方式避免复杂的线性扫描。
