前面我们学习了数组、链表、栈、队列、哈希表等数据结构，它们有一个共同点：数据之间的关系都是「线性」的（一个接一个）或者「层级」的（树形结构）。但现实世界中很多关系不是这么简单的——比如社交网络中，每个人都可以和任意多的人成为好友；城市之间，多条公路相互交错。这种「多对多」的关系，用图（Graph）来表达最为自然。1. 什么是图图（Graph）由两部分组成：顶点（Vertex）：也叫节点，表示实体。比如社交网络中的每个人、地图上的每个城市。边（Edge）：表示两个顶点之间的关系。比如两个人是好友、两个城市之间有公路相连。用数学语言来说，一个图 G = (V, E)，其中 V 是顶点的集合，E 是边的集合。1.1 图的分类根据边的性质，图分为两类：无向图：边没有方向。如果 A 和 B 之间有边，表示 A 到 B 和 B 到 A 都是可达的。社交网络中的「好友关系」就是无向图——你是我的好友，我也是你的好友。有向图：边有方向。从 A 到 B 的边不代表从 B 到 A 也能走。微博的「关注」关系就是有向图——你关注了某人，不代表某人也关注了你。根据边是否带有权重，还可以分为带权图（每条边有一个数值，比如公路的距离）和无权图（边只有连接关系，没有额外信息）。2. 图的存储方式在程序中，图有两种最常见的存储方式：邻接矩阵和邻接表。2.1 邻接矩阵邻接矩阵是一个二维数组matrix[n][n]，其中n是顶点的数量。如果顶点 i 和顶点 j 之间有边，则matrix[i][j] = 1（无权图）或matrix[i][j] = 权重（带权图）。假设有一个无向图，4 个顶点（0、1、2、3），边为 (0,1)、(0,2)、(1,2)、(2,3)：0 --- 1 | / | / 2 --- 3对应的邻接矩阵：0 1 2 3 0 [ 0, 1, 1, 0 ] 1 [ 1, 0, 1, 0 ] 2 [ 1, 1, 0, 1 ] 3 [ 0, 0, 1, 0 ]无向图的邻接矩阵沿对角线对称——(0,1)有边意味着matrix[0][1]和matrix[1][0]都是 1。在 C++ 中实现：constintN=4;intmatrix[N][N]={};// 添加边 (u, v)voidaddEdge(intu,intv){matrix[u][v]=1;matrix[v][u]=1;// 无向图，两边都要标记}邻接矩阵的优点是查询两点之间是否有边的时间复杂度为 O(1)，实现简单。缺点是空间复杂度为 O(n²)，当顶点很多但边很少（稀疏图）时，会浪费大量空间。2.2 邻接表邻接表的思路是：每个顶点维护一个列表，记录它连接的所有顶点。还是上面的例子，邻接表表示为：0 → [1, 2] 1 → [0, 2] 2 → [0, 1, 3] 3 → [2]在 C++ 中，通常用vector数组来实现：constintN=4;vectorintadj[N];// 添加边 (u, v)voidaddEdge(