现在的位置: 首页 > 综合 > 正文

算法导论22.4-2 有向无环图的路径数目

2017年12月15日 ⁄ 综合 ⁄ 共 154字 ⁄ 字号 评论关闭

要求在一个有向无环图中,给定两点,求出这两点之间有多少条路径。

该章节是讲拓扑排序,考虑先拓扑排序,将图排序成P336页的图22-7类似的样子,然后对E(s, t)之间的部分进行DP

可以证明所有路径都仅存在于s, t之间。

递归式如下(L(s, t)表示s到t的路径的数目):



直接用DFS好像是不可行的,代码就不写了。

抱歉!评论已关闭.