C#中无环有向图(DAG)的向上遍历相关算法与实现疑问

问题解答 #

1. 递归遍历的算法名称 #

该递归式遍历所有节点的算法是反向深度优先搜索（反向DFS，Depth-First Search），也可称为递归深度优先遍历：因为原图边方向为自上而下，向上遍历需要沿ToNodeId指向FromNodeId的反向边行进，递归实现的遍历逻辑本质是深度优先搜索的定向变种。

2. 遍历起始点选择 #

你需要以**所有出度为0的节点（DAG汇点）**作为遍历起始点：

• 你的DAG所有边均为自上而下指向，出度为0的节点就是没有下游节点的最底层节点，刚好匹配从下往上的遍历方向要求。
• 你可以直接基于持有的Edge列表统计节点出度：遍历所有Edge，每遇到一个FromNodeId就给对应节点的出度计数加1，最终出度为0的节点就是所有起始点。
• 你已有的自上而下排序的Edge列表可以简化统计逻辑：排序越靠后的Edge对应的ToNodeId越接近底层，优先校验这些节点的出度可以减少遍历统计的成本。

关联类定义（格式化后） #

class Edge
{
   public string FromNodeId {get; set;}
   public string ToNodeId{get; set;}
}

class Node
{
   public int Id {get; set;}
   public string Name {get; set;}
}

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