给定一个无向图和一棵树（表示为父数组），如何确定是否可以通过在给定图上应用广度优先搜索来生成给定树？ BFS 遍历是否有特定的属性可以用来识别矛盾？
BFS 遍历是否有特定的属性可以用来识别矛盾？
是的。 BFS 的一个关键属性是按照与起始节点的距离的顺序来访问节点。
考虑给定树的根是起始节点，然后从图中的该节点执行真正的 BFS，记下节点与根节点的距离。
如果这些距离与这些节点在给定树中的深度相同，则确定，否则我们就有矛盾。