邻接表使用哈希表或数组存储每个顶点及其相邻顶点的列表。
邻接表是图论中最常用的图表示方式之一,它为每个顶点维护一个列表,存储与该顶点相邻的所有顶点。这种表示方法特别适合表示稀疏图(边数远小于顶点数平方的图),能有效节省空间,保持较高的操作效率。
邻接表(Adjacency List)是一种通过链表或数组表示图的数据结构。在理解它之前,我们需要掌握一些基础图论概念:
图(Graph):由顶点(Vertex)和连接顶点的边(Edge)组成的数据结构。图可以用来表示现实世界中的各种关系,如社交网络、交通系统等。
顶点(Vertex):图中的节点,通常用数字或字母标识,如 0, 1, 2... 或 A, B, C...
边(Edge):连接两个顶点的线段,表示它们之间存在某种关系。
在邻接表中:
邻接表的表示方式根据图的类型有所不同:
无向图中:
有向图中:
示例:
假设有一个包含 4 个顶点 (0, 1, 2, 3) 的无向图,边的信息如下:
则其邻接表表示为:
▼Plain复制代码0 -> [1, 2] 1 -> [0, 2] 2 -> [0, 1, 3] 3 -> [2]
对于有权图,每个邻接表项通常包含顶点索引和边的权重。
▼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复制代码# 邻接表表示的图 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复制代码// 邻接表表示的图 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复制代码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++复制代码#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; } } };
优点:
缺点:
对于有向图,除了常规邻接表外,可以同时维护一个反向邻接表,存储指向每个顶点的所有顶点。这种双重结构在一些算法中非常有用,如:
对于静态图(边不会频繁变化),可以使用压缩邻接表(CSR, Compressed Sparse Row)格式来进一步降低内存消耗。CSR 使用两个数组:
这种表示方法在大规模图计算中常用,如 PageRank 算法。
邻接表特别适合实现图遍历算法,如广度优先搜索(BFS)和深度优先搜索(DFS)。这些算法是许多更复杂路径查询的基础:
在实际应用中,邻接表可以增强存储更多信息:
选择图表示方法时的一般准则:
在大规模图应用中,节省内存特别重要。邻接表可以通过以下方式进一步优化:
测验答案
- 600个顶点引用。在无向图的邻接表中,每条边在两个顶点的列表中各出现一次,所以总共有 300 * 2 = 600 个顶点引用。
- O(V+E)。使用标准邻接表无法直接获取入度,需要遍历所有顶点的邻接表,检查是否包含目标顶点。
- O(V+E)。需要遍历所有顶点的邻接表,总工作量与顶点数加边数成正比。