图

图是一种由顶点和边组成的结构。顶点可以想象成“地点”，边是连接地点的“道路”。比如地铁图：每个站是顶点，线路是边。图用来表示事物之间的任意关系，非常灵活。

无向图的边没有方向，像双向道路，两人可以互相访问。有向图的边有箭头，像单行道，只能从一个顶点到另一个。带权图的边带有数值（权重），比如距离或时间，用来表示“代价”。

邻接矩阵用二维数组存储，matrix[i][j] 表示顶点 i 到 j 是否有边（或权重）。适合稠密图，但浪费空间。邻接表为每个顶点维护一个链表，只存实际存在的边，节省空间，适合稀疏图。选择哪种取决于图的边数。

BFS（广度优先搜索）从起点开始，一层层向外访问，像水波扩散，适合找最短路径。DFS（深度优先搜索）沿着一条路走到底，再回头，像走迷宫。两者都需要 visited 数组记录已访问顶点，避免重复和死循环。

图算法广泛应用于社交网络、地图导航、任务调度等场景。理解基本概念后，就能应对大部分面试和工程问题。