【大模型2609·数据结构算法·07】网状拓扑结构：图的邻接表示法与深度/广度优先遍历

kikock2026-10-112026-10-11

专栏导读：图结构是复杂拓扑关系与知识图谱的底层支撑。本篇系统梳理有向图、无向图、带权图的核心概念，对比邻接矩阵与邻接表在稠密/稀疏图下的空间与性能表现，并深度演示基于队列的广度优先搜索（BFS）与基于栈/递归的深度优先搜索（DFS）实战范式。

图

前面我们学习了线性结构和树，线性结构局限于只有一个直接前驱和一个直接后继的关系，树也只能有一个直接前驱，也就是父节点，当我们需要表示多对多的关系时，就需要用到图了，图是比树更普遍的结构，可以认为树是一种特殊的图。图由节点和边组成。

图的常见术语：

节点：也称为顶点，是图的基础部分。

边：连接两个节点，也是图的基础部分。可以是单向的，也可以是双向的。

权重：边可以添加“权重”变量。

邻接：两节点之间存在边，则称这两个节点邻接。

度：一个节点的边的数量。入度为指向该节点的边的数量，出度为该节点指向其他节点的边的数量。

路径：从一节点到另一节点所经过的边的序列。

环：首尾节点相同的路径。

有向图：边是单向的。

无向图：边是双向的。

连通图：从某个节点出发，可以到达其余任意节点。

非连通图：从某个节点出发，有节点不可达。

邻接矩阵用一个n×n的矩阵来表示有n个节点之间的关系，矩阵的每一行（列）代表一个节点，矩阵m行n列的值代表是否存在由m指向n的边。邻接矩阵适合存储稠密图。

邻接表存储n个链表、列表或其他容器，每个容器存储该节点的所有邻接节点。邻接表适合存储稀疏图，空间效率高，尤其在处理边远少于节点的图时表现优越，但在进行边查找时不如邻接矩阵高效。

广度优先搜索（BFS，Breadth First Search）从起始节点开始，首先访问该节点的所有邻接节点，然后再访问邻接节点的邻接节点，依此类推，逐层访问节点。

从图的起始节点开始，首先访问该节点，并标记为已访问。

然后依次访问所有未被访问的邻接节点，并将它们加入到队列中。

当队列中的节点被访问时，继续访问它的邻接节点，并将新的节点加入队列。

直到队列为空，表示所有节点都已被访问。

深度优先搜索（DFS，Depth First Search）尽可能地深入到图的每一个分支，直到不能再深入为止，然后回溯到上一个节点，继续尝试其他的分支。

从图的一个起始节点开始，访问这个节点并标记为已访问。

对于每个未访问的邻接节点，递归地执行 DFS，直到没有未访问的邻接节点。

当回溯到一个节点时，继续访问它的其他邻接节点。