对于给定的有向无环图,我正在寻找一种方法来验证包含活动的列表是否可行。一个节省资源的解决方案会很好,因为G的大小可能会急剧增加
示例:
G = {0: [], 1: [0], 2: [0], 3: [0], 4: [1], 5: [1], 6: [4], 7: [4], 8: [3,6,7], 9: [2,5,6], 10: [2,5], 11: [8,9,10]}
现在这个名单
L1 = [0, 1, 2, 3, 4, 5, 10, 6, 7, 9, 8, 11]
例如是可行的,但是
L2 = [1, 0, 2, 3, 4, 10, 5, 6, 7, 9, 8, 11]
不是,因为活动0是1的前身,而活动5是10的前身
我理解这个问题,你想检查一个给定的节点顺序是否与图中边定义的偏序一致。也许我遗漏了一些东西,但是对于这一点,检查所有边
a -> b
就足够了,即列表中a
的索引低于b
的索引。如果您首先创建一个字典,将元素映射到它们的位置,那么其复杂性将仅为O(e)
,e
即边数相关问题 更多 >
编程相关推荐