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

Question

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

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

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

Answer 1

以下递归算法可以解决您的问题。请注意，您的输入图实际上并不是一棵树，而是一个 DAG (但是，该算法也适用于 DAG)。我假设你的 DAG 是 topologically sorted并且您将 DAG 的根提供给 group 函数。如果您的 DAG 未按拓扑排序，则应首先执行拓扑排序，这可以使用 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