寻求可将有根有向图转换为功能图的图论算法

提问：我偶然看到了Marek Chrobak撰写的论文，文中提出了将非确定性有限自动机转换为确定性有限自动机的方法，即带环加尾结构的自动机。请问图论领域是否存在功能类似的算法，可将有根有向图转换为功能图（每个节点恰好有一条出边的图）？

这类算法确实存在，核心逻辑和Chrobak构造规范自动机的思路同源，都是通过结构规约/重构在保证核心语义（可达性/状态转移等价）的前提下，把多转移的结构收敛为单转移结构，常见的实现分为两类：

• 出边裁剪规约算法：适用于仅要求满足功能图出度为1的结构约束、对语义等价要求较低的场景。实现逻辑是遍历所有节点，按照预设规则（如边权最小优先、DFS遍历顺序优先、邻接节点编号排序优先）为每个节点保留唯一一条出边，其余出边直接裁剪，整体时间复杂度为O(V+E)。如果需要保留原图的可达性，可对裁剪掉的分支做节点拆分挂载，类似Chrobak算法里的尾节点挂载到环的逻辑，不改变路径终点的前提下把多分支收敛为单出边。
• 幂集展开构造算法：适用于要求构造的功能图和原图完全语义等价（即保留所有可达性信息）的场景，逻辑和自动机的子集构造法完全对齐：把原图的节点子集作为新功能图的节点，每个新节点的唯一出边指向「原子集内所有节点的出边邻接节点」构成的新子集，直到没有新子集生成即可。构造完成的功能图完全保留了原图的所有路径可达特征，和Chrobak算法的语义等价性要求一致。

内容的提问来源于stack exchange，提问作者blobee