将具有单个后继节点的树节点分组的算法

Question

我有一个像下面这样的图形数据结构。

将只有一个子节点的节点分组为一个节点的算法是什么？例如，上面的树将被转换成如下：

图可以有任意长度的节点链，也可以自己回环。

Answer 1

下面的递归算法解决了你的问题。请注意，您的输入图并不是真正的树，而是 DAG (however, the algorithm works properly on DAGs too). I'm assuming that your DAG is topologically sorted and that you feed the DAG's root to the group function. If your DAG is not topologically sorted, you should first perform a topological sort, which can be done in linear time using DFS.

group(dag_node):
   if dag_node.num_children == 0:
      new_node = new DagNode(dag_node.value)
   if dag_node.num_children > 1:
      new_node = new DagNode(dag_node.value)
      new_node.children = [group(child) for child in dag_node.children]
   if tree_node.num_children == 1:
      value_pair = (dag_node.value, dag_node.children[0].value)
      new_node = new DagNode(value_pair)
      new_node.children = dag_node.children[0].children
      new_node = group(new_node)
   return new_node

将具有单个后继节点的树节点分组的算法

Algorithm to group tree nodes with single successors

algorithm

tree

grouping