给出线性时间算法来测试树是否具有完美匹配,即,一组边缘仅接触树的每个椎骨一次.
这是来自S. Dasgupta的Algorithms,我似乎无法解决这个问题.我知道我需要以某种方式使用贪婪的方法,但我无法弄清楚这一点.救命？
伪代码很好; 一旦我有了这个想法,我就可以用任何语言轻松实现.
算法必须是线性的.O(V + E)很好.
我想我有解决方案.由于我们知道图是树,因此我们知道叶节点的存在,具有一个边的节点而没有子节点.为了使该节点包含在完美匹配中,该边缘必须存在于最终解决方案中.
因此,我们可以找到连接到叶节点的所有边,添加到解决方案中,并从图中移除触摸的边.如果在此过程结束时,我们留下任何剩余的未播放节点,则不存在完美匹配.