图的宽度优先搜索树与最短路径树 基本定义 在连通图 \( G = (V, E) \) 中，从某一顶点 \( s \)（源点）出发进行宽度优先搜索（BFS），会生成一棵 BFS树 \( T \)。这棵树满足： 树根为 \( s \)； 对于任意顶点 \( v \)，树中从 \( s \) 到 \( v \) 的路径是原图中从 \( s \) 到 \( v \) 的 最短路径 （按边数计算）。 BFS树的特点是同一层的顶点到源点的距离相同。 BFS树的构造与性质 BFS通过队列逐层访问顶点： 初始化：将 \( s \) 标记为距离 \( 0 \)，入队； 迭代：取出队首顶点 \( u \)，遍历其未访问的邻居 \( v \)，将 \( v \) 的距离设为 \( d(u) + 1 \)，并添加边 \( (u, v) \) 到BFS树中； 终止：队列为空时，所有可达顶点均被访问。 关键性质 ：BFS树中从 \( s \) 到 \( v \) 的路径长度等于 \( v \) 在BFS中的距离标签 \( d(v) \)。 最短路径树（SPT）的推广 若图为 带权图 （边权非负），BFS树无法保证最短性，此时需使用 Dijkstra算法 生成 最短路径树（SPT） ： SPT是以 \( s \) 为根的树，树上从 \( s \) 到任意 \( v \) 的路径是原图中带权意义下的最短路径； 当边权均为1时，SPT退化为BFS树。 Dijkstra算法通过优先队列按距离递增顺序访问顶点，逐步扩展SPT。 SPT的唯一性与非唯一性 若图中从 \( s \) 到某顶点 \( v \) 存在多条最短路径，则SPT可能不唯一（任选一条路径即可）； 若所有边权互异，则SPT唯一； 对于无负权环的图，SPT可通过Bellman-Ford算法构造，但此时树结构可能因负权边而复杂化。 应用与扩展 路由协议 ：网络中的OSPF协议使用SPT计算最短路径； 层次布局 ：BFS树用于社交网络中的距离分析； 动态SPT ：当边权变化时，增量算法可高效更新SPT。 研究前沿包括分布式SPT算法、容错SPT（边失效场景）等。