将 DAG 转换为二叉树
Converting a DAG to Binary Tree
我正在尝试将 DAG 转换为二叉树。考虑下图
我希望上面的树有以下输出。
由于A,B,C,E形成了一个菱形，要将其转化为一棵树，我需要将B和C移动成一条线。
我试过以下方法：
- 拓扑排序：输出为 A -> D -> B -> C -> E -> F 。
- 拓扑排序顺序：A -> [B,C,D] -> E -> F
拓扑路径为我们提供了一条直线路径。但是，我想尽可能保留序列，即 A -> D。但是，如果有菱形，我希望一个节点只有一个父节点并对这些父节点进行排序。
对于上述情况，有没有办法从 DAG 生成树？
算法伪代码
Run a topological sort on the graph
For every node B, in reverse order of the topological sort:
If B has more than one parent:
Order its parents A1, A2, ..., An in the order of the topological sort
For every i in 1..n-1:
Add an arc from Ai to A(i+1)
Remove the arc from Ai to B
正确性证明
- 算法总是终止，因为它是一个固定长度的循环；它的时间复杂度是
O(N^2) 其中 N 是节点数
- 紧接在给定节点 B 上的步骤之后，B 不超过一个父节点
- 如果给定节点C上的步骤已经执行，则在拓扑顺序中C之前的节点B上执行步骤只会向拓扑顺序中C之前的节点添加弧；因此，一旦执行了节点的步骤，它们就永远不会获得新的父节点。
证明算法终止，执行算法后每个节点至多有一个父节点。由于我们只从具有多个父节点的节点中删除父节点，我认为它也可以满足您的问题。
我正在尝试将 DAG 转换为二叉树。考虑下图
我希望上面的树有以下输出。
由于A,B,C,E形成了一个菱形，要将其转化为一棵树，我需要将B和C移动成一条线。
我试过以下方法：
- 拓扑排序：输出为 A -> D -> B -> C -> E -> F 。
- 拓扑排序顺序：A -> [B,C,D] -> E -> F
拓扑路径为我们提供了一条直线路径。但是，我想尽可能保留序列，即 A -> D。但是，如果有菱形，我希望一个节点只有一个父节点并对这些父节点进行排序。
对于上述情况，有没有办法从 DAG 生成树？
算法伪代码
Run a topological sort on the graph
For every node B, in reverse order of the topological sort:
If B has more than one parent:
Order its parents A1, A2, ..., An in the order of the topological sort
For every i in 1..n-1:
Add an arc from Ai to A(i+1)
Remove the arc from Ai to B
正确性证明
- 算法总是终止，因为它是一个固定长度的循环；它的时间复杂度是
O(N^2)其中N是节点数 - 紧接在给定节点 B 上的步骤之后，B 不超过一个父节点
- 如果给定节点C上的步骤已经执行，则在拓扑顺序中C之前的节点B上执行步骤只会向拓扑顺序中C之前的节点添加弧；因此，一旦执行了节点的步骤，它们就永远不会获得新的父节点。
证明算法终止，执行算法后每个节点至多有一个父节点。由于我们只从具有多个父节点的节点中删除父节点，我认为它也可以满足您的问题。