图数据结构邻接矩阵与邻接表：C++/Java/Python 3种实现对比与性能分析

图数据结构邻接矩阵与邻接表：C++/Java/Python 3种实现对比与性能分析

在计算机科学领域，图（Graph）作为一种非线性数据结构，广泛应用于社交网络分析、路径规划、推荐系统等场景。本文将深入探讨图的两种核心存储方式——邻接矩阵与邻接表，并基于C++、Java、Python三种主流编程语言进行实现对比与性能分析。

1. 图数据结构基础概念

图由**顶点（Vertex）和边（Edge）**组成，可分为有向图和无向图。理解这两种存储结构前，需要明确几个关键指标：

• 空间复杂度：存储图所需的内存空间
• 时间复杂度：常见操作（如查询邻接节点）的执行效率
• 适用场景：不同图特征（稀疏/稠密）下的最优选择

提示：在实际工程中，图结构的选择往往需要在空间效率与时间效率之间权衡，没有绝对优劣之分。

2. 邻接矩阵实现与对比

邻接矩阵使用二维数组表示顶点间的连接关系，矩阵中的值可以表示边的存在与否或权重。

2.1 C++实现

#include <iostream> #include <vector> class AdjMatrixGraph { private: std::vector<std::vector<int>> matrix; int vertexCount; public: AdjMatrixGraph(int n) : vertexCount(n), matrix(n, std::vector<int>(n, 0)) {} void addEdge(int i, int j, int weight = 1) { matrix[i][j] = weight; matrix[j][i] = weight; // 无向图需对称设置 } void printMatrix() { for (const auto& row : matrix) { for (int val : row) { std::cout << val << " "; } std::cout << std::endl; } } };

2.2 Java实现

public class AdjMatrixGraph { private int[][] matrix; private int vertexCount; public AdjMatrixGraph(int vertexCount) { this.vertexCount = vertexCount; this.matrix = new int[vertexCount][vertexCount]; } public void addEdge(int i, int j, int weight) { matrix[i][j] = weight; matrix[j][i] = weight; // 无向图对称设置 } public void printMatrix() { for (int[] row : matrix) { for (int val : row) { System.out.print(val + " "); } System.out.println(); } } }

2.3 Python实现

class AdjMatrixGraph: def __init__(self, vertex_count): self.vertex_count = vertex_count self.matrix = [[0] * vertex_count for _ in range(vertex_count)] def add_edge(self, i, j, weight=1): self.matrix[i][j] = weight self.matrix[j][i] = weight # 无向图对称设置 def print_matrix(self): for row in self.matrix: print(" ".join(map(str, row)))

2.4 性能对比

注意：Python由于动态类型和列表实现，在大型矩阵处理上性能明显低于C++/Java

3. 邻接表实现与对比

邻接表为每个顶点维护一个链表，存储其相邻顶点，更适合稀疏图。

3.1 C++实现（使用STL）

#include <iostream> #include <list> #include <vector> class AdjListGraph { private: std::vector<std::list<std::pair<int, int>>> adjList; // pair<vertex, weight> public: AdjListGraph(int vertexCount) : adjList(vertexCount) {} void addEdge(int src, int dest, int weight = 1) { adjList[src].emplace_back(dest, weight); adjList[dest].emplace_back(src, weight); // 无向图 } void printList() { for (int i = 0; i < adjList.size(); ++i) { std::cout << i << ": "; for (const auto& edge : adjList[i]) { std::cout << "(" << edge.first << "," << edge.second << ") "; } std::cout << std::endl; } } };

3.2 Java实现

import java.util.*; public class AdjListGraph { private List<List<Edge>> adjList; class Edge { int dest; int weight; Edge(int dest, int weight) { this.dest = dest; this.weight = weight; } } public AdjListGraph(int vertexCount) { adjList = new ArrayList<>(vertexCount); for (int i = 0; i < vertexCount; i++) { adjList.add(new LinkedList<>()); } } public void addEdge(int src, int dest, int weight) { adjList.get(src).add(new Edge(dest, weight)); adjList.get(dest).add(new Edge(src, weight)); // 无向图 } }

3.3 Python实现

from collections import defaultdict class AdjListGraph: def __init__(self): self.graph = defaultdict(list) def add_edge(self, u, v, weight=1): self.graph[u].append((v, weight)) self.graph[v].append((u, weight)) # 无向图 def print_list(self): for vertex in self.graph: print(f"{vertex}: {self.graph[vertex]}")

3.4 性能对比

4. 存储结构与算法性能分析

4.1 空间复杂度对比

4.2 常见操作时间复杂度

4.3 三种语言实现性能测试数据

使用1000个顶点、5000条边的随机图进行测试：

5. 工程实践建议

根据实际项目需求选择合适实现：

1. 超大规模图处理：

   • 优先考虑C++实现
   • 使用内存池优化邻接表节点分配
   • 考虑压缩稀疏矩阵存储

2. 快速开发场景：

   • Python + NetworkX库（内置高效图算法）
   • 对性能关键部分使用Cython加速

3. 企业级应用：

   • Java实现提供更好的可维护性
   • 使用Trove等高效集合库替代标准集合

# Python优化示例：使用numpy实现邻接矩阵 import numpy as np class OptimizedAdjMatrix: def __init__(self, size): self.matrix = np.zeros((size, size), dtype=np.int32) def add_edge(self, i, j, weight=1): self.matrix[i][j] = weight self.matrix[j][i] = weight

对于现代图数据处理，还可以考虑以下优化策略：

• 并行化处理：利用多线程加速矩阵运算
• 内存布局优化：使用结构体数组替代类对象
• 缓存友好设计：优化数据访问模式减少缓存未命中