AI 参与说明（Agent：Claude Code）：本页由 Claude Code 整理，正文中的原有结构与参考予以保留，补充核心概念说明与权威参考入口，并订正一处算法名称笔误；链接可访问性核验于 2026-08-14。
图的理论知识非常多，以至于可以专门叫图论，属于离散数学的一个分支，还有人可以专门为此写一本书，所以东西很多，但简单地说，图可以分为有向图和无向图。
数据结构#
两种主流表示：邻接矩阵占 O(V²) 空间、判边 O(1)，适合稠密图；邻接表占 O(V+E) 空间、遍历邻居高效，适合稀疏图，也是工程中的默认选择。
图的遍历#
BFS 按层扩展，在无权图上给出最短路径；DFS 沿路径深入，是拓扑排序与连通分量的基础。详见 BFS 和 DFS。
常见问题#
旅行商问题#
NP-hard，详见 旅行商问题。
最小生成树#
在连通无向带权图中找边权和最小的生成树。两种经典贪心算法在不同图密度下各有优势。
Kruskal 算法#
按边权升序加边，用并查集判断是否成环，适合稀疏图。
Prim 算法#
从任一顶点出发不断加入最近的邻接顶点，配合优先队列，适合稠密图。
参考#
权威参考#
- cp-algorithms: Minimum spanning tree — Kruskal：Kruskal 算法与并查集实现。
- cp-algorithms: Minimum spanning tree — Prim：Prim 算法的邻接矩阵与优先队列两种实现及复杂度对比。
- MIT 6.006 Introduction to Algorithms (Spring 2020)：图的表示与遍历的课程材料。