图 Graph

数据结构 · 顶点和边的任意连接（最一般的结构）

什么是图

树是「一个父亲、向下分叉」的特例；图则彻底放开——任意几个顶点之间，想连就连一条边，可以成环、可以多对多。地图路网、社交关系、网页链接，本质都是图。

图怎么遍历（不重不漏地走遍所有顶点）？两条经典路线，正好把前面学的队列和栈用上了——选个起点，点 BFS 或 DFS 看它们怎么走（点顶点可换起点）。

亲手试试

点 BFS 或 DFS 开始

点一个顶点设为起点，再点 BFS 或 DFS。当前起点：A。

看出区别了吗——BFS（广度优先）像水波：用一个队列，先把起点的邻居全排队，再一圈圈向外，一层层访问；DFS（深度优先）像走迷宫：用一个栈（或递归），一条道走到底，撞墙了再回头换路。BFS 能找最短路（边数最少），DFS 适合探路 / 找连通块。

图常用两种存法：邻接表（每个顶点挂一串邻居，省空间、适合稀疏图）和邻接矩阵（一张 N×N 表，matrix[i][j]=1 表示 i、j 相连，查两点是否相邻 O(1)）。

路网 / 导航：顶点是地点、边是路，最短路就是 BFS / Dijkstra。
社交网络：顶点是人、边是关注，找共同好友、做推荐。
依赖 / 调度：任务依赖图，拓扑排序定执行顺序。

到这里，从线性的栈、队列、数组、链表，到非线性的树、堆、哈希表、图——数据结构这一程就走完了。它们其实是同一件事的不同取舍：怎么把数据组织好，让该快的操作快起来。