图论（易混淆概念）

Python 库比较 #

评分说明:

易用性: 学习曲线、API 直观性、安装复杂度。 性能 (通用图分析): 处理非 GNN 图算法（如路径、中心性）的速度，尤其针对大规模图。 性能 (GNN): 训练和推理图神经网络的速度，包括 GPU 加速能力。 (N/A 表示该库不专注于 GNN) 功能丰富度 (通用图分析): 内建图算法、图操作、格式支持的广度。 功能丰富度 (GNN): GNN 层、模型、数据集加载器等的全面性。 (N/A 表示该库不专注于 GNN) 社区活跃度/支持: 文档质量、教程示例、社区问答响应速度、用户基数。

NetworkX:

定位: 通用图论算法库，纯 Python 实现。 优点: 易用性极高，功能全面，可视化方便。 缺点: 纯 Python 实现，大规模图性能受限。 社区活跃度: 非常高。拥有庞大的用户群，悠久的历史，丰富的文档、教程和示例，GitHub 仓库活跃，问题响应快。 适用场景: 教学、快速原型、中小型图分析、网络科学入门。

igraph (python-igraph):

定位: 高性能图论库，核心由 C 语言编写。 优点: 性能优越，内存效率高，功能丰富。 缺点: 安装可能稍复杂，API 风格与 NetworkX 不同。 社区活跃度: 高。有专门的论坛和邮件列表，文档完善，开发持续，但用户基数和讨论热度可能不及 NetworkX。 适用场景: 大规模图的通用分析、性能要求高的场景、网络科学研究。

PyG (PyTorch Geometric):

定位: 基于 PyTorch 的图神经网络（GNN）库。 优点: 专注于 GNN，性能高（GPU 加速），与 PyTorch 生态结合紧密，更新快。 缺点: 通用图分析功能相对较少，需要 GNN 和 PyTorch 基础。 社区活跃度: 非常高。作为主流 GNN 库之一，GitHub 活跃，论文复现多，有专门的 Slack 频道和讨论区，社区响应迅速。 适用场景: 图神经网络研究与应用（基于 PyTorch）。

DGL (Deep Graph Library):

定位: 专注于图神经网络的库，支持多种深度学习后端。 优点: GNN 支持全面，多后端支持（PyTorch, TensorFlow, MXNet），性能高（GPU 加速）。 缺点: 通用图分析非其重点，需要 GNN 和相应框架基础。 社区活跃度: 非常高。另一个主流 GNN 库，GitHub 活跃，文档和示例丰富，有专门的讨论论坛，社区支持良好。 适用场景: 图神经网络研究与应用，特别是需要多后端支持或看重其特定设计的场景。

rustworkx:

定位: 高性能图论库，核心由 Rust 编写。 优点: 性能极高，内存安全（得益于 Rust），API 设计简洁，与 Python 集成良好。最初为 Qiskit (量子计算框架) 开发，通用性强。 缺点: 相对较新，通用图算法的覆盖面可能仍在追赶 NetworkX 或 igraph，可视化支持不如 NetworkX 直接。 社区活跃度: 中等。虽然增长迅速且受到关注（尤其是在需要高性能的领域），但用户基数和社区历史积累相比 NetworkX/igraph/PyG/DGL 尚有差距。GitHub 仓库活跃，开发者响应积极。 适用场景: 极高性能要求的图算法、需要 Rust 级别性能和安全性的场景、作为其他 Python 项目（如 Qiskit）的底层图库。 总结比较表:

ref: Gemini

基本概念 #

注：假设任意两顶点间最多一条边。

（无向）完全图：有 n（n-1）/2 条边

连通图：无向图中，任意两个顶点是连通的（一个顶点不必与另一个顶点直接相连，可以通过其它顶点到达即可）最少有 n-1 条边

非连通图，即边数少于 n-1 条，最多有（n-1）*(n-2)/2 条

连通分量：无向图中（区别于有向图）的极大连通子图，极大即要求拥有连通子图的所有边

强连通图：有向图中，从 a 到 b 和从 b 到 a 都有路径。最少有 n 条边，假若少了 A-D 的路径，则 A 可以到 D，但是 D 到不了 A，就不满足条件。

强连通分量：有向图中的极大强连通子图，对比无向图中连通分量。

生成树：包含图中全部顶点的一个极小连通子图。若去除一条边，则生成树会变成非连通图；若多加上一条边，则会形成回路。（注意：生成树不唯一）

注意：极大连通子图要求连通子图包含所有边，极小连通子图要求使图保存连通的前提下使边数最少。

简单路径：顶点不重复出现的路径称为简单路径

区分：无向图关于连通图和连通分量，有向图关于强连通图和强连通分量

ref, bak