邻接表
介绍
邻接表是图论中最常用的图表示方式之一，它为每个顶点维护一个列表，存储与该顶点相邻的所有顶点。这种表示方法特别适合表示稀疏图（边数远小于顶点数平方的图），能有效节省空间，保持较高的操作效率。
基本概念
邻接表（Adjacency List）是一种通过链表或数组表示图的数据结构。在理解它之前，我们需要掌握一些基础图论概念：
图（Graph）：由顶点（Vertex）和连接顶点的边（Edge）组成的数据结构。图可以用来表示现实世界中的各种关系，如社交网络、交通系统等。
顶点（Vertex）：图中的节点，通常用数字或字母标识，如 0, 1, 2... 或 A, B, C...
边（Edge）：连接两个顶点的线段，表示它们之间存在某种关系。
在邻接表中：
每个顶点对应一个列表（可以是链表、数组或其他集合类型）
列表中存储与该顶点直接相连的所有顶点
对于有权图，还需要存储边的权重信息
邻接表的表示方式根据图的类型有所不同：
无向图中：
如果顶点 i 和 j 之间有边，则 j 会出现在 i 的邻接表中，i 也会出现在 j 的邻接表中
每条边在两个不同的列表中各出现一次
有向图中：
如果从顶点 i 到 j 有一条边，则 j 只会出现在 i 的邻接表中
每条边只在一个列表中出现一次
示例：
假设有一个包含 4 个顶点 (0, 1, 2, 3) 的无向图，边的信息如下：
0 连接到 1
0 连接到 2
1 连接到 2
2 连接到 3
则其邻接表表示为：
▼Plain复制代码0 -> [1, 2]
1 -> [0, 2]
2 -> [0, 1, 3]
3 -> [2]
对于有权图，每个邻接表项通常包含顶点索引和边的权重。
核心特性
空间效率高：只需存储实际存在的边，特别适合稀疏图
快速访问某个顶点的所有邻接点
灵活：容易添加和删除边，同时支持添加额外的边信息（如权重）
适用于各种图算法，如广度优先搜索（BFS）和深度优先搜索（DFS）
基本操作
添加边：将目标顶点添加到源顶点的邻接列表中
删除边：从源顶点的邻接列表中删除目标顶点
查询边：检查目标顶点是否在源顶点的邻接列表中
获取顶点的所有邻接点：直接访问该顶点的邻接列表
基础实现
代码实现
Java
▼Java复制代码import java.util.*;
// 邻接表表示的图
class Graph {
private int V; // 顶点数
private List
// 构造函数
public Graph(int v) {
this.V = v;
adjList = new ArrayList<>(v);
for (int i = 0; i < v; i++) {
adjList.add(new ArrayList<>());
}
}
// 添加边（无向图）
public void addEdge(int source, int destination) {
// 确保顶点有效
if (source >= 0 && source < V && destination >= 0 && destination < V) {
adjList.get(source).add(destination);
adjList.get(destination).add(source); // 对于无向图，两个方向都要添加
}
}
// 删除边
public void removeEdge(int source, int destination) {
if (source >= 0 && source < V && destination >= 0 && destination < V) {
adjList.get(source).remove(Integer.valueOf(destination));
adjList.get(destination).remove(Integer.valueOf(source)); // 对于无向图，两个方向都要删除
}
}
// 判断两个顶点之间是否有边
public boolean hasEdge(int source, int destination) {
if (source >= 0 && source < V && destination >= 0 && destination < V) {
return adjList.get(source).contains(destination);
}
return false;
}
// 获取顶点的所有邻接点
public List
if (vertex >= 0 && vertex < V) {
return new ArrayList<>(adjList.get(vertex));
}
return new ArrayList<>();
}
// 打印邻接表
public void printGraph() {
for (int i = 0; i < V; i++) {
System.out.print(i + " -> ");
for (int j : adjList.get(i)) {
System.out.print(j + " ");
}
System.out.println();
}
}
}
// 有权图的邻接表实现
class WeightedGraph {
private int V;
private List
// 内部类表示有权边
class Edge {
int destination;
int weight;
public Edge(int destination, int weight) {
this.destination = destination;
this.weight = weight;
}
}
// 构造函数
public WeightedGraph(int v) {
this.V = v;
adjList = new ArrayList<>(v);
for (int i = 0; i < v; i++) {
adjList.add(new ArrayList<>());
}
}
// 添加边（有权图）
public void addEdge(int source, int destination, int weight) {
if (source >= 0 && source < V && destination >= 0 && destination < V) {
adjList.get(source).add(new Edge(destination, weight));
adjList.get(destination).add(new Edge(source, weight)); // 对于无向图
}
}
// 获取边的权重
public int getEdgeWeight(int source, int destination) {
if (source >= 0 && source < V && destination >= 0 && destination < V) {
for (Edge edge : adjList.get(source)) {
if (edge.destination == destination) {
return edge.weight;
}
}
}
return -1; // 表示没有边或顶点无效
}
// 打印有权图
public void printGraph() {
for (int i = 0; i < V; i++) {
System.out.print(i + " -> ");
for (Edge edge : adjList.get(i)) {
System.out.print("(" + edge.destination + "," + edge.weight + ") ");
}
System.out.println();
}
}
}
Python
▼Python复制代码# 邻接表表示的图
class Graph:
def __init__(self, v):
self.V = v # 顶点数
self.adj_list = [[] for _ in range(v)] # 邻接表（无权图）
# 添加边（无向图）
def add_edge(self, source, destination):
# 确保顶点有效
if 0 <= source < self.V and 0 <= destination < self.V:
self.adj_list[source].append(destination)
self.adj_list[destination].append(source) # 对于无向图，两个方向都要添加
# 删除边
def remove_edge(self, source, destination):
if 0 <= source < self.V and 0 <= destination < self.V:
if destination in self.adj_list[source]:
self.adj_list[source].remove(destination)
if source in self.adj_list[destination]:
self.adj_list[destination].remove(source) # 对于无向图，两个方向都要删除
# 判断两个顶点之间是否有边
def has_edge(self, source, destination):
if 0 <= source < self.V and 0 <= destination < self.V:
return destination in self.adj_list[source]
return False
# 获取顶点的所有邻接点
def get_adjacent_vertices(self, vertex):
if 0 <= vertex < self.V:
return self.adj_list[vertex].copy()
return []
# 打印邻接表
def print_graph(self):
for i in range(self.V):
print(f"{i} -> {' '.join(map(str, self.adj_list[i]))}")
# 有权图的邻接表实现
class WeightedGraph:
def __init__(self, v):
self.V = v
self.adj_list = [[] for _ in range(v)]
# 添加边（有权图）
def add_edge(self, source, destination, weight):
if 0 <= source < self.V and 0 <= destination < self.V:
self.adj_list[source].append((destination, weight))
self.adj_list[destination].append((source, weight)) # 对于无向图
# 获取边的权重
def get_edge_weight(self, source, destination):
if 0 <= source < self.V and 0 <= destination < self.V:
for dest, weight in self.adj_list[source]:
if dest == destination:
return weight
return -1 # 表示没有边或顶点无效
# 打印有权图
def print_graph(self):
for i in range(self.V):
print(f"{i} -> {' '.join([f'({d},{w})' for d, w in self.adj_list[i]])}")
JavaScript
▼Javascript复制代码// 邻接表表示的图
class Graph {
constructor(v) {
this.V = v; // 顶点数
this.adjList = Array(v).fill().map(() => []); // 邻接表（无权图）
}
// 添加边（无向图）
addEdge(source, destination) {
// 确保顶点有效
if (source >= 0 && source < this.V && destination >= 0 && destination < this.V) {
this.adjList[source].push(destination);
this.adjList[destination].push(source); // 对于无向图，两个方向都要添加
}
}
// 删除边
removeEdge(source, destination) {
if (source >= 0 && source < this.V && destination >= 0 && destination < this.V) {
this.adjList[source] = this.adjList[source].filter(v => v !== destination);
this.adjList[destination] = this.adjList[destination].filter(v => v !== source);
}
}
// 判断两个顶点之间是否有边
hasEdge(source, destination) {
if (source >= 0 && source < this.V && destination >= 0 && destination < this.V) {
return this.adjList[source].includes(destination);
}
return false;
}
// 获取顶点的所有邻接点
getAdjacentVertices(vertex) {
if (vertex >= 0 && vertex < this.V) {
return [...this.adjList[vertex]];
}
return [];
}
// 打印邻接表
printGraph() {
for (let i = 0; i < this.V; i++) {
console.log(`${i} -> ${this.adjList[i].join(' ')}`);
}
}
}
// 有权图的邻接表实现
class WeightedGraph {
constructor(v) {
this.V = v;
this.adjList = Array(v).fill().map(() => []);
}
// 添加边（有权图）
addEdge(source, destination, weight) {
if (source >= 0 && source < this.V && destination >= 0 && destination < this.V) {
this.adjList[source].push({destination, weight});
this.adjList[destination].push({destination: source, weight}); // 对于无向图
}
}
// 获取边的权重
getEdgeWeight(source, destination) {
if (source >= 0 && source < this.V && destination >= 0 && destination < this.V) {
const edge = this.adjList[source].find(e => e.destination === destination);
return edge ? edge.weight : -1;
}
return -1; // 表示没有边或顶点无效
}
// 打印有权图
printGraph() {
for (let i = 0; i < this.V; i++) {
const edges = this.adjList[i].map(e => `(${e.destination},${e.weight})`).join(' ');
console.log(`${i} -> ${edges}`);
}
}
}
Go
▼Go复制代码package main
import "fmt"
// Graph 邻接表表示的图（无权图）
type Graph struct {
V int // 顶点数
AdjList [][]int // 邻接表
}
// NewGraph 创建新图
func NewGraph(v int) *Graph {
adjList := make([][]int, v)
for i := range adjList {
adjList[i] = make([]int, 0)
}
return &Graph{
V: v,
AdjList: adjList,
}
}
// AddEdge 添加边（无向图）
func (g *Graph) AddEdge(source, destination int) {
// 确保顶点有效
if source >= 0 && source < g.V && destination >= 0 && destination < g.V {
g.AdjList[source] = append(g.AdjList[source], destination)
g.AdjList[destination] = append(g.AdjList[destination], source) // 对于无向图，两个方向都要添加
}
}
// RemoveEdge 删除边
func (g *Graph) RemoveEdge(source, destination int) {
if source >= 0 && source < g.V && destination >= 0 && destination < g.V {
// 从source的邻接表中删除destination
for i, v := range g.AdjList[source] {
if v == destination {
g.AdjList[source] = append(g.AdjList[source][:i], g.AdjList[source][i+1:]...)
break
}
}
// 从destination的邻接表中删除source
for i, v := range g.AdjList[destination] {
if v == source {
g.AdjList[destination] = append(g.AdjList[destination][:i], g.AdjList[destination][i+1:]...)
break
}
}
}
}
// HasEdge 判断两个顶点之间是否有边
func (g *Graph) HasEdge(source, destination int) bool {
if source >= 0 && source < g.V && destination >= 0 && destination < g.V {
for _, v := range g.AdjList[source] {
if v == destination {
return true
}
}
}
return false
}
// GetAdjacentVertices 获取顶点的所有邻接点
func (g *Graph) GetAdjacentVertices(vertex int) []int {
if vertex >= 0 && vertex < g.V {
// 创建副本以避免修改原始列表
result := make([]int, len(g.AdjList[vertex]))
copy(result, g.AdjList[vertex])
return result
}
return []int{}
}
// PrintGraph 打印邻接表
func (g *Graph) PrintGraph() {
for i := 0; i < g.V; i++ {
fmt.Printf("%d -> ", i)
for _, v := range g.AdjList[i] {
fmt.Printf("%d ", v)
}
fmt.Println()
}
}
// Edge 有权图中的边
type Edge struct {
Destination int
Weight int
}
// WeightedGraph 有权图的邻接表实现
type WeightedGraph struct {
V int // 顶点数
AdjList [][]Edge // 邻接表
}
// NewWeightedGraph 创建新的有权图
func NewWeightedGraph(v int) *WeightedGraph {
adjList := make([][]Edge, v)
for i := range adjList {
adjList[i] = make([]Edge, 0)
}
return &WeightedGraph{
V: v,
AdjList: adjList,
}
}
// AddEdge 添加边（有权图）
func (g *WeightedGraph) AddEdge(source, destination, weight int) {
if source >= 0 && source < g.V && destination >= 0 && destination < g.V {
g.AdjList[source] = append(g.AdjList[source], Edge{Destination: destination, Weight: weight})
g.AdjList[destination] = append(g.AdjList[destination], Edge{Destination: source, Weight: weight}) // 对于无向图
}
}
// GetEdgeWeight 获取边的权重
func (g *WeightedGraph) GetEdgeWeight(source, destination int) int {
if source >= 0 && source < g.V && destination >= 0 && destination < g.V {
for _, edge := range g.AdjList[source] {
if edge.Destination == destination {
return edge.Weight
}
}
}
return -1 // 表示没有边或顶点无效
}
// PrintGraph 打印有权图
func (g *WeightedGraph) PrintGraph() {
for i := 0; i < g.V; i++ {
fmt.Printf("%d -> ", i)
for _, edge := range g.AdjList[i] {
fmt.Printf("(%d,%d) ", edge.Destination, edge.Weight)
}
fmt.Println()
}
}
C++
▼C++复制代码#include
#include
#include
// 邻接表表示的图（无权图）
class Graph {
private:
int V; // 顶点数
std::vector
public:
// 构造函数
Graph(int v) {
this->V = v;
adjList.resize(v);
}
// 添加边（无向图）
void addEdge(int source, int destination) {
// 确保顶点有效
if (source >= 0 && source < V && destination >= 0 && destination < V) {
adjList[source].push_back(destination);
adjList[destination].push_back(source); // 对于无向图，两个方向都要添加
}
}
// 删除边
void removeEdge(int source, int destination) {
if (source >= 0 && source < V && destination >= 0 && destination < V) {
// 从source的邻接表中删除destination
adjList[source].erase(
std::remove(adjList[source].begin(), adjList[source].end(), destination),
adjList[source].end()
);
// 从destination的邻接表中删除source
adjList[destination].erase(
std::remove(adjList[destination].begin(), adjList[destination].end(), source),
adjList[destination].end()
);
}
}
// 判断两个顶点之间是否有边
bool hasEdge(int source, int destination) {
if (source >= 0 && source < V && destination >= 0 && destination < V) {
return std::find(adjList[source].begin(), adjList[source].end(), destination) != adjList[source].end();
}
return false;
}
// 获取顶点的所有邻接点
std::vector
if (vertex >= 0 && vertex < V) {
return adjList[vertex];
}
return std::vector
}
// 打印邻接表
void printGraph() {
for (int i = 0; i < V; i++) {
std::cout << i << " -> ";
for (int j : adjList[i]) {
std::cout << j << " ";
}
std::cout << std::endl;
}
}
};
// 有权图中的边
struct Edge {
int destination;
int weight;
Edge(int dest, int w) : destination(dest), weight(w) {}
};
// 有权图的邻接表实现
class WeightedGraph {
private:
int V; // 顶点数
std::vector
public:
// 构造函数
WeightedGraph(int v) {
this->V = v;
adjList.resize(v);
}
// 添加边（有权图）
void addEdge(int source, int destination, int weight) {
if (source >= 0 && source < V && destination >= 0 && destination < V) {
adjList[source].push_back(Edge(destination, weight));
adjList[destination].push_back(Edge(source, weight)); // 对于无向图
}
}
// 获取边的权重
int getEdgeWeight(int source, int destination) {
if (source >= 0 && source < V && destination >= 0 && destination < V) {
for (const Edge& edge : adjList[source]) {
if (edge.destination == destination) {
return edge.weight;
}
}
}
return -1; // 表示没有边或顶点无效
}
// 打印有权图
void printGraph() {
for (int i = 0; i < V; i++) {
std::cout << i << " -> ";
for (const Edge& edge : adjList[i]) {
std::cout << "(" << edge.destination << "," << edge.weight << ") ";
}
std::cout << std::endl;
}
}
};
优缺点
优点：
空间效率高：对于稀疏图，只需存储实际存在的边
添加顶点操作简单：只需添加一个新的空列表
遍历顶点的所有邻接点高效：直接访问对应列表
适合与大多数图算法结合使用，如 BFS、DFS、Dijkstra 等
内存使用灵活：随着边的增加，动态分配内存
缺点：
查询特定边的存在性需要遍历列表，时间复杂度为 O(度)
删除边操作较慢，需要遍历列表查找目标顶点
对于完全图或近似完全图，内存消耗与邻接矩阵相当甚至更多
对于无向图，每条边需要存储两次，可能导致不一致性
应用场景
表示大多数实际应用中的稀疏图
社交网络的关系表示（如朋友关系、关注关系）
网络路由中的节点连接关系
图遍历算法的实现（如 BFS、DFS）
最短路径算法（如 Dijkstra、Bellman-Ford）
最小生成树算法（如 Prim 算法）
扩展
邻接表的优化与变体
反向邻接表
对于有向图，除了常规邻接表外，可以同时维护一个反向邻接表，存储指向每个顶点的所有顶点。这种双重结构在一些算法中非常有用，如：
强连通分量算法（如 Kosaraju 算法）
计算顶点的入度
反向遍历图
压缩邻接表
对于静态图（边不会频繁变化），可以使用压缩邻接表（CSR, Compressed Sparse Row）格式来进一步降低内存消耗。CSR 使用两个数组：
一个存储所有邻接点，按顶点顺序排列
另一个存储每个顶点邻接列表的起始索引
这种表示方法在大规模图计算中常用，如 PageRank 算法。
高级应用
复杂路径查询
邻接表特别适合实现图遍历算法，如广度优先搜索（BFS）和深度优先搜索（DFS）。这些算法是许多更复杂路径查询的基础：
最短路径查找（Dijkstra 和 Bellman-Ford 算法）
所有节点对之间的最短路径（Floyd-Warshall 算法）
欧拉路径和汉密尔顿路径查找
增强邻接表
在实际应用中，邻接表可以增强存储更多信息：
为边添加时间戳（表示关系建立的时间）
存储边的类型（如社交网络中的"朋友"、"关注"等不同关系）
为边添加状态信息（如交通网络中道路的拥堵状况）
与其他表示方法的比较选择
选择图表示方法时的一般准则：
稀疏图（|E| << |V|²）：首选邻接表，空间复杂度为 O(V+E)
密集图（|E| 接近 |V|²）：邻接矩阵可能更有效，空间复杂度为 O(V²)
需要快速查询特定边：邻接矩阵提供 O(1) 查询时间
需要频繁添加/删除顶点：邻接表更灵活
需要在所有边上迭代：边列表更直接
内存效率考虑
在大规模图应用中，节省内存特别重要。邻接表可以通过以下方式进一步优化：
使用整数索引代替对象引用
采用适当的数据结构存储邻接点（比如有序数组可支持二分查找）
使用哈希表或平衡树代替普通列表，加速搜索特定边的过程
测验
在一个包含 100 个顶点和 300 条边的无向图中，如果使用邻接表表示，共需要存储多少个顶点引用？
对于一个有向图，如果要判断某个顶点的入度（指向该顶点的边数），使用邻接表需要怎样的时间复杂度？
在邻接表表示的图中，遍历所有边的时间复杂度是多少？（V 表示顶点数，E 表示边数）
测验答案
600个顶点引用。在无向图的邻接表中，每条边在两个顶点的列表中各出现一次，所以总共有 300 * 2 = 600 个顶点引用。
O(V+E)。使用标准邻接表无法直接获取入度，需要遍历所有顶点的邻接表，检查是否包含目标顶点。
O(V+E)。需要遍历所有顶点的邻接表，总工作量与顶点数加边数成正比。
相关的 LeetCode 热门题目
133. 克隆图 - 要求深拷贝一个无向图，邻接表是最适合的表示方法
207. 课程表 - 判断有向图是否有环，可以使用邻接表表示课程依赖关系
210. 课程表 II - 基于邻接表的拓扑排序问题
547. 省份数量 - 可以使用邻接表表示城市间的连接关系，然后计算连通分量数