邻接表

图算法

邻接表使用哈希表或数组存储每个顶点及其相邻顶点的列表。

空间复杂度:O(V + E)

算法讲解

邻接表

介绍

邻接表是图论中最常用的图表示方式之一,它为每个顶点维护一个列表,存储与该顶点相邻的所有顶点。这种表示方法特别适合表示稀疏图(边数远小于顶点数平方的图),能有效节省空间,保持较高的操作效率。

基本概念

邻接表(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<List<Integer>> adjList; // 邻接表(无权图) // 构造函数 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<Integer> getAdjacentVertices(int vertex) { 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<List<Edge>> adjList; // 内部类表示有权边 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 <iostream> #include <vector> #include <algorithm> // 邻接表表示的图(无权图) class Graph { private: int V; // 顶点数 std::vector<std::vector<int>> adjList; // 邻接表 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<int> getAdjacentVertices(int vertex) { if (vertex >= 0 && vertex < V) { return adjList[vertex]; } return std::vector<int>(); } // 打印邻接表 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<std::vector<Edge>> adjList; // 邻接表 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) 查询时间
  • 需要频繁添加/删除顶点:邻接表更灵活
  • 需要在所有边上迭代:边列表更直接

内存效率考虑

在大规模图应用中,节省内存特别重要。邻接表可以通过以下方式进一步优化:

  • 使用整数索引代替对象引用
  • 采用适当的数据结构存储邻接点(比如有序数组可支持二分查找)
  • 使用哈希表或平衡树代替普通列表,加速搜索特定边的过程

测验

  1. 在一个包含 100 个顶点和 300 条边的无向图中,如果使用邻接表表示,共需要存储多少个顶点引用?
  2. 对于一个有向图,如果要判断某个顶点的入度(指向该顶点的边数),使用邻接表需要怎样的时间复杂度?
  3. 在邻接表表示的图中,遍历所有边的时间复杂度是多少?(V 表示顶点数,E 表示边数)

测验答案

  1. 600个顶点引用。在无向图的邻接表中,每条边在两个顶点的列表中各出现一次,所以总共有 300 * 2 = 600 个顶点引用。
  2. O(V+E)。使用标准邻接表无法直接获取入度,需要遍历所有顶点的邻接表,检查是否包含目标顶点。
  3. O(V+E)。需要遍历所有顶点的邻接表,总工作量与顶点数加边数成正比。

相关的 LeetCode 热门题目

  • 133. 克隆图 - 要求深拷贝一个无向图,邻接表是最适合的表示方法
  • 207. 课程表 - 判断有向图是否有环,可以使用邻接表表示课程依赖关系
  • 210. 课程表 II - 基于邻接表的拓扑排序问题
  • 547. 省份数量 - 可以使用邻接表表示城市间的连接关系,然后计算连通分量数