graph - 树证书的顶点度数

Question

给定一棵树作为证书，例如

00010111

如何在不重建树的情况下计算图中顶点的度数？或者只是找到最大度数的顶点？

标签： graphtheory

Answer 1

事实证明，该解决方案相当简单，只需要通过输入证书一次。伪代码如下：

S = new stack of int
max_degree = 0

for i=1 to length( certificate )
 if certificate[i] == 0
   current = S.pop()
   if ( current != null ) 
     current = current +1
     S.push( current )
   S.push( 0 )   
 else
   current = S.pop()
   if ( i != length( certificate ) )
     current = current +1
   if ( current > max_degree )
     max_degree = current

变量 max_degree 包含遍历整个证书后图中节点的最大度数