mun*_*air 19 algorithm graph-theory breadth-first-search binary-search-tree
我不需要代码,只需要解释.我的教科书说
级别顺序:级别i的每个节点在级别i + 1的任何节点之前被处理
我对广度优先搜索的理解是你从左边开始首先探索离根最近的节点？这有什么不同？这是一个方形和矩形的情况吗？
Duk*_*ing 18
对于"正确的"树(见下文),它是相同的,至少大多数定义.像维基百科一样,例如:
广度优先
另请参见:广度优先搜索
树也可以在水平顺序中遍历,......
...广度优先(水平顺序)遍历......
好吧,至少水平顺序遍历与广度优先遍历相同.遍历某些东西有很多理由,它不仅仅是搜索,因为广度优先搜索似乎意味着,尽管许多(或大多数)没有做出这种区分并且可以互换地使用这些术语.
我个人真正使用"级别顺序遍历"的唯一一次是在讨论in-,post-和pre-order遍历时,只是遵循相同的"......顺序遍历"格式.
对于一般图形,"水平"的概念可能不是很好(尽管你可以将它定义为距离源节点的(最短)距离,我想),因此水平顺序遍历可能不太好 - 定义,但广度优先搜索仍然很有意义.
我在上面提到了一个"正确的"树(这是一个完全构成的子分类,以防你想知道) - 这只是意味着'水平'被定义为你所期望的 - 每个边缘将水平增加一个.然而,人们可能能够稍微使用"级别"的定义(尽管这可能不被广泛接受),实质上允许边跳过级别(或者甚至在同一级别上的节点之间具有边缘).例如:
level
1 1
/ \
2 / 3
/ /
3 2 4
因此,水平顺序遍历将是1, 3, 2, 4,
而广度优先遍历将是1, 2, 3, 4.