图结构

图由顶点和边组成，表示多对多关系，是最通用的非线性数据结构。

分类

维度	类型	说明
边方向	无向图 / 有向图	边是否带方向
边权重	无权图 / 带权图	边是否带数值代价
连通性	连通图 / 非连通图	是否存在孤岛

表示方法

方法	空间	查邻接	适用场景
邻接矩阵			稠密图
邻接表			稀疏图、通用

遍历

• DFS：递归/栈，沿一条路径深入到底再回溯
• BFS：队列，逐层扩展，求最短路径（无权图）

典型算法

• 最短路径：Dijkstra、Bellman-Ford、Floyd-Warshall
• 最小生成树：Prim、Kruskal
• 拓扑排序：Kahn 算法（入度 + BFS）