检查一个图的拓扑顺序是否在另一个图中保持
Checking if topological ordering of one graph is maintained in another
如果我有一组节点 N 和一组顶点 V_1 定义了具有特定拓扑顺序的图 G_1，我如何检查来自 N 的节点和定义图 G_2 的一组新顶点 V_2 保持 G_1?
的拓扑顺序
例如
G_1:
D -> E
B -> C
A -> C
G_1 的拓扑排序：[A, B, C, D, E]
G_2:
D -> B
B -> E
G_2的拓扑排序：[D, B, E]
我正在考虑某种蛮力方法，我生成 G_1 的所有拓扑排序，从这些排序中删除 G_2 中未找到的节点，并检查是否有任何匹配第一个排序找到 G_2.
我的潜在解决方案是否正确？你有什么更好的建议吗？
我认为你的解决方案是正确的，但效率低下。
对于一些糟糕的情况（G_2 是一个循环，所以没有拓扑排序，G_1 没有边，所以任何排序都是拓扑的）你最终会做 O(N!*N)。
更好的解决方案是计算满足两个图的拓扑顺序。
在标准拓扑排序算法中，您会计算传入的边。在每一步中，您都选择一个计数为 0 的节点，将其添加到解决方案中，减少所有传出边的计数并继续，直到没有更多节点可供选择或所有节点都具有非零计数（一个循环）。
我建议您为两个图表保留两组计数。选择一个在两个集合中计数都为 0 的节点（即，在两个图中都是有效的下一个选择）并根据它们的传出链接更新两个图中的计数。
如果你完成了所有的节点，那么你就找到了一个对两个图都是拓扑排序的排序，否则就没有这样的排序。
如果可以，您还可以合并这两个图，并使用标准算法对合并后的图计算拓扑排序。结果（如果有的话）应该是两个原始图的有效拓扑排序。
两种解决方案（如果实施正确）的复杂度均为 O(N)。
如果我有一组节点 N 和一组顶点 V_1 定义了具有特定拓扑顺序的图 G_1，我如何检查来自 N 的节点和定义图 G_2 的一组新顶点 V_2 保持 G_1?
例如
G_1:
D -> E
B -> C
A -> C
G_1 的拓扑排序：[A, B, C, D, E]
G_2:
D -> B
B -> E
G_2的拓扑排序：[D, B, E]
我正在考虑某种蛮力方法，我生成 G_1 的所有拓扑排序，从这些排序中删除 G_2 中未找到的节点，并检查是否有任何匹配第一个排序找到 G_2.
我的潜在解决方案是否正确？你有什么更好的建议吗？
我认为你的解决方案是正确的，但效率低下。
对于一些糟糕的情况（G_2 是一个循环，所以没有拓扑排序，G_1 没有边，所以任何排序都是拓扑的）你最终会做 O(N!*N)。
更好的解决方案是计算满足两个图的拓扑顺序。
在标准拓扑排序算法中，您会计算传入的边。在每一步中，您都选择一个计数为 0 的节点，将其添加到解决方案中，减少所有传出边的计数并继续，直到没有更多节点可供选择或所有节点都具有非零计数（一个循环）。
我建议您为两个图表保留两组计数。选择一个在两个集合中计数都为 0 的节点（即，在两个图中都是有效的下一个选择）并根据它们的传出链接更新两个图中的计数。 如果你完成了所有的节点，那么你就找到了一个对两个图都是拓扑排序的排序，否则就没有这样的排序。
如果可以，您还可以合并这两个图，并使用标准算法对合并后的图计算拓扑排序。结果（如果有的话）应该是两个原始图的有效拓扑排序。
两种解决方案（如果实施正确）的复杂度均为 O(N)。