Ano*_*ith 3 algorithm tree breadth-first-search tree-traversal graph-algorithm
好吧,我知道无向图的广度优先搜索树不能有后沿.但我想知道它怎么能有一个跨界？我无法对由OFS构造的图形G的生成树进行成像,其中包含一个交叉边缘.
在无向图上使用BFS构建生成树的过程将生成以下类型的边:
一个简单的例子:想象一个三角形(一个三角形团) - 从任何节点开始一个BFS,你将在第一步到达另外两个.您在它们之间留下了不属于生成树的边缘.
后边缘(连接祖先和非直接孩子)怎么样？好吧,正如你所指出的那样,在BFS中,在无向图上你将不会拥有它们,因为你在第一次到达祖先时会使用那个边缘.
实际上,你可以做一个更强的语句 - 所有非树边缘应该在顶点之间作为相同的级别,或者相邻的级别(如果另一侧的顶点是兄弟,则不能将该边缘用于树,例如在三角形的情况下,或父母的兄弟姐妹,尚未探索过).无论哪种方式,它都属于跨边界的定义.