检查有向无环图是否可行
质素
对于给定的有向无环图G，我正在寻找一种方法来验证包含活动的列表L是否优先。由于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的前身。
tobias_k
据我了解的问题，您想检查给定的节点顺序是否与图中边缘定义的部分顺序一致。也许我失去了一些东西，但对于这一点，应该是足够检查所有边缘a ---> b该指数a在列表比指数更低b。如果首先创建一个将元素映射到其位置的字典，则其复杂度仅为O(e)，e即边数。
def check(g, l):
pos = {x: i for i, x in enumerate(l)} # for O(1) index
return all(pos[a] < pos[b] for b in g for a in g[b])
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]
print(check(G, L1)) # True
print(check(G, L2)) # False
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
通过有向无环图存储唯一路径是否可行？
- 2
有向无环图的函数定义
- 3
有向无环图的拓扑排序
- 4
选择单个有向无环图
- 5
从给定“根”的无向无环图创建有向无环图
- 6
如何检查给定无向图是否有传递方向？
- 7
如何检查给定无向图是否有传递方向？
- 8
带负边的有向无环图的Dijkstra算法
- 9
如何找到有向无环图的最大独立集？
- 10
安全地遍历有向无环图
- 11
d3.js中的有向无环图
- 12
本体的图形布局算法（有向无环图）
- 13
有向无环 k 部分图的自动布局
- 14
连通无向无环图与树
- 15
无向图，检查节点之间是否存在路径
- 16
在jgrapht中修剪有向无环图的更有效方法吗？
- 17
需要对DAG（有向无环图）进行一些澄清
- 18
使用不带DOT的d3.js的有向无环图
- 19
如何在R中绘制有向无环格子图
- 20
VBA 使有向图无向
- 21
如何将一组节点划分为每个形成有向无环图的子集
- 22
有向无环图中的循环检测更快？
- 23
Dijkstra是针对有向图还是无向图的算法？
- 24
无向图的着色
- 25
无向图的A *算法
- 26
检查有向图CS50 tideman中是否存在循环
- 27
O（m + n）算法检查有向图是否单边连接
- 28
列举有向无环图中的所有路径
- 29
有向无环图中所有节点的可达性计数
我来说两句