图

概述

图由顶点与边构成，用于描述多对多的关系。根据边的方向与权重可分为有向图/无向图、带权图/无权图。

基本概念

• 顶点（V）：图中的元素。
• 边（E）：顶点之间的连接关系。
• 度：与顶点相连的边的数量（有向图还区分入度/出度）。
• 路径：从一个顶点到另一个顶点的顶点序列。

存储方式

• 邻接矩阵：适合稠密图，查询边存在性快，空间占用高。
• 邻接表：适合稀疏图，空间占用低，遍历效率高。

基本操作与遍历

• 深度优先搜索（DFS）。
• 广度优先搜索（BFS）。

常见问题

• 最短路径（Dijkstra、Floyd）。
• 最小生成树（Prim、Kruskal）。