1

在解决一个在线编码网站的问题时,我遇到了这个问题。是否有任何算法可以找到给定无向图中的线性生成树的数量,使得生成树中的每个节点最多有一个孩子?

4

1 回答 1

0

根据问题,我认为它只是要求查找单线节点的数量。单线我的意思是如果图表是

      o
     /
o-o-o-o
   \   \
    o-o-o

所以线性生成树之一将是:

      o
     /
o-o-o

要找到这样的树,您可以使用 dfs。

于 2013-06-13T14:03:28.370 回答