我无法理解算法设计手册中的 BFS 树边
I cannot understand BFS Tree Edges in Algorithm Design Manual
我不明白这是什么意思
The graph edges that do not appear in the breadth-first search tree also
have special properties. For undirected graphs, non-tree edges can point only
to vertices on the same level as the parent vertex, or to vertices on the level
directly below the parent. These properties follow easily from the fact that each
path in the tree must be a shortest path in the graph. For a directed graph,
a back-pointing edge (u, v) can exist whenever v lies closer to the root than u
does.
我理解'广度优先搜索树中没有出现的图边也
具有特殊属性。但是我怎么知道这些 属性 很容易从树中的每条路径必须是图中的最短路径这一事实中得出呢？另外，对于有向图，对于有向图，只要 v 比 u 更靠近根，我如何证明反向边 (u, v) 可以存在？
因为我们使用的是 BFS 树，树的同一级别中的所有节点必须与根节点的距离相同。因此，例如，深度为五的节点必须与根节点的距离为五。同样，深度为 10 的节点必须与根的距离为 10。
首先说说无向图。假设有一条边 {u, v} 不在 BFS 树中。现在，假设 u 和 v 在树中相隔两层以上，具体来说 v 至少比 u 低两层。这意味着从根节点 s 到 v 的距离比从 s 到 u 的距离多两倍。因此，从 s 到 v 的最短路径的长度至少比从 s 到 u 的最短路径的长度多两条边（这是最短路径的定义）。但这不是真的：我们可以得到一条从 s 到 v 的路径，它只比从 s 到 u 的最短路径长一条边，方法是沿着从 s 到 u 的最短路径，然后沿着边 {u, v}。这里出了点问题，特别是我们假设 v 比 u 低两个或更多级别。
对于有向图，您确实可以使用有向边跳回树中的更高级别。一种非常简单的理解方式：考虑一个由节点 u、v、w 组成的三角形，其中 u 有一条到 v 的边，v 有一条到 w 的边，w 有一条到 u 的边。 BFS树长什么样？
我不明白这是什么意思
The graph edges that do not appear in the breadth-first search tree also have special properties. For undirected graphs, non-tree edges can point only to vertices on the same level as the parent vertex, or to vertices on the level directly below the parent. These properties follow easily from the fact that each path in the tree must be a shortest path in the graph. For a directed graph, a back-pointing edge (u, v) can exist whenever v lies closer to the root than u does.
我理解'广度优先搜索树中没有出现的图边也 具有特殊属性。但是我怎么知道这些 属性 很容易从树中的每条路径必须是图中的最短路径这一事实中得出呢？另外，对于有向图，对于有向图，只要 v 比 u 更靠近根，我如何证明反向边 (u, v) 可以存在？
因为我们使用的是 BFS 树，树的同一级别中的所有节点必须与根节点的距离相同。因此，例如，深度为五的节点必须与根节点的距离为五。同样，深度为 10 的节点必须与根的距离为 10。
首先说说无向图。假设有一条边 {u, v} 不在 BFS 树中。现在，假设 u 和 v 在树中相隔两层以上，具体来说 v 至少比 u 低两层。这意味着从根节点 s 到 v 的距离比从 s 到 u 的距离多两倍。因此，从 s 到 v 的最短路径的长度至少比从 s 到 u 的最短路径的长度多两条边（这是最短路径的定义）。但这不是真的：我们可以得到一条从 s 到 v 的路径，它只比从 s 到 u 的最短路径长一条边，方法是沿着从 s 到 u 的最短路径，然后沿着边 {u, v}。这里出了点问题，特别是我们假设 v 比 u 低两个或更多级别。
对于有向图，您确实可以使用有向边跳回树中的更高级别。一种非常简单的理解方式：考虑一个由节点 u、v、w 组成的三角形，其中 u 有一条到 v 的边，v 有一条到 w 的边，w 有一条到 u 的边。 BFS树长什么样？