相同顶点集下树T可作为图G的BFS树的判定算法求解问题

核心结论 #

只要满足以下两个充要条件，就一定存在符合要求的G的邻接表排序：

• 树T的所有边都属于无向图G的边集
• 无向图G中任意一条边连接的两个顶点，在树T中的深度差不超过1（需先指定T的根节点，也就是BFS的起始节点）

高效算法步骤 #

时间复杂度为O(V+E)，其中V为顶点总数，E为G的边总数：

• 步骤1：指定BFS的起始顶点s，即树T的根节点；若题目未给出s，可任选T的根，最终结果仅对应该根下的BFS树。
• 步骤2：对T执行一次DFS或BFS遍历，计算每个顶点v在T中的深度depth[v]，同时记录T的所有边。
• 步骤3：校验T的所有边是否都存在于G的边集中，只要有一条边不存在，直接返回不存在符合要求的邻接表。
• 步骤4：遍历G的所有边(u, v)，校验abs(depth[u] - depth[v]) <= 1是否成立，只要有一条边不满足，直接返回不存在符合要求的邻接表。
• 步骤5：所有校验通过则返回存在符合要求的邻接表，构造方式为：每个顶点的邻接表优先放置它在T中的所有子节点，剩余邻居按任意顺序排列即可，按该邻接表从s出发运行BFS，生成的树恰好为T。

充要性说明 #

必要性：BFS树的边必然是原图的边，因此T的边都要在G中存在；BFS的层次遍历性质决定了原图任意边连接的两个顶点深度差最多为1，否则会违反BFS的遍历规则。
充分性：满足两个条件时，将T的子节点排在邻接表最前，BFS遍历到当前节点时会优先访问这些未被访问的子节点并将其加入树结构，其余邻居要么已被访问，要么是同层顶点，不会改变生成树的结构。

内容的提问来源于stack exchange，提问作者food panda