使用图遍历来测试一个图是一个完美的二叉树

Question

当给定由邻接列表表示的无向图G时，如何使用DFS来查看该图是否是完美的二叉树？

我已经能够识别边缘情况：例如，对于深度D，你需要2^n-1个节点，你可以使用对数计算出最大深度，如果这不是全部，你知道你没有一个完美的树，但我想不出使用邻接列表和DFS进行测试的有效方法。

Answer 1

在一个不为空的完美二叉树中𝑛节点，我们有这些属性：

• 节点数𝑛小于2的幂一，即。ℎ=日志₂(𝑛+1( 是整数。𝑛=2^ℎ−1
• 边的数量为𝑛−1
• 没有超过3个邻居的节点
• 何时𝑛 >1，(只有(一个节点正好有2个邻居：它是根
• 何时𝑛 >1，树的叶子只有一个邻居：有2^ℎ-其中1
• 根和任何叶子之间的距离为ℎ−1

可以逐个检查这些属性。一旦确定了根，就可以执行遍历来检查距离属性。使用DFS或BFS。

Answer 2

如果图为空，或者只有一个顶点，则返回true。

否则，请检查以确保图形是连接的和非循环的。

那么，如果它是一个完美的二叉树，那么它必须只有一个2度的顶点。这就是根源。设CCD_ 1和CCD_。然后：

let depthA = depthIfPerfect(a, root);
let depthB = depthIfPerfect(b, root);
return depthA == depthB && depthA >=0

其中：

depthIfPerfect(node, parent):
if degree(node) == 1:
return 1;
if degree(node) != 3:
return -1; //not perfect
let a and b be the neighbors that aren't parent
let depthA = depthIfPerfect(a, node);
let depthB = depthIfPerfect(b, node);

if (depthA != depthB || depthA < 0):
return -1: //not perfect
return depthA+1;

如果您愿意，可以将连通性和非循环性的检查混合到这个遍历中。