algorithm - DAG，查找顶点子集的边

Question

我有一个 DAG G=(V,E)，它是邻接表表示。我正在尝试根据附加到顶点的一些参数来压缩它。

现在我有一个图 G=(V,E) 和一个包含 V 子集的列表。

知道如何有效地从原始图中找到子集顶点的边吗？

我需要使用原始图连接子集。

看这张图

{9: [10], 7: [9], 8: [9], 6: [7], 3: [8], 2: [3, 4], 5: [4, 6], 4: [ 7]，1：[2]}

现在如果我取子集 [1,4,7]

如何找到子集的连接？请参阅传递闭包作为一个问题。我需要在传递闭包中找到所有边，但不是重复项。

Answer 1

如果你的子集是 S，你可以做 |S| 深度优先搜索（或广度优先搜索）以确定子集图中的边。每次搜索都是O(V+E)，所以如果 S 很小，那就是O(V^2+VE)或更好的O(S(V+E)) 。然后，您可能希望使用传递缩减来删除不必要的边缘。

如果你的图不是完全无环的，它几乎肯定会帮助首先合并强连接的组件。这样做很便宜，并且可以大大减少所需的工作。

Answer 2

首先，您将不得不利用一些算法来获得传递闭包。从您的示例看来，该图非常稀疏，因此请使用Johnson's Algorithm而不是 Floyd-Warshall 。对于稀疏图，约翰逊的算法需要 O((V^2)*log V + VE)，这比 Floyd-Warshall 的 O(V^3) 少。请注意，只有当您有一个大的稀疏图时，这种差异才会明显。

现在，如果 x 可从 y 到达（这将由 Johnson 算法给出），则为子集图中的每对顶点添加形式 < x,y> 的边。

Answer 3

将子集（我们称之为S）放入哈希表中。然后遍历邻接表并查看每条边的第一个顶点是否在哈希表中。这样你就可以在O (| S | + | E |) 中得到你想要的所有边。

Answer 4

一个简单的方法是找到原始图的传递闭包（使用Floyd-Warshall），然后使用它将边添加到结果图中。

通过找到传递闭包，您有一个邻接矩阵，其中当原始图中的顶点 x 和 y 之间存在任何路径（直接或间接）时，matrix[x][y] 为真。使用它，您可以简单地为子图中的每对顶点 a 和 b 添加边 (a,b)，如果 matrix[a][b] 为真（即原始图中存在从 a 到 b 的路径）。

这最终会添加比严格必要的更多的边，但它会给你一个准确的子集图。