代码之家 › 专栏 › 技术社区 › YAKOVM

有向图到子图的划分

directed-acyclic-graphs partitioning graph-theory algorithm

YAKOVM · 技术社区 · 15 年前

如果我们将DAG的高度定义为从某个源到某个汇的最大路径长度。

我们要求生成的所有子图的高度大致相同。

每对节点集(子图)的交集为空。

您可以在附图中看到右分区的示例(图中的每条边都向上)。

alt text

在这个例子中有36个节点和8个汇点[#10,11,12,13,20,21,22,23],所以每个子图应该有6个节点和2或3个汇点。

你对算法有什么想法吗?

非常感谢你

1 回复 | 直到 15 年前

amit 15 年前

你应该在每个子图中有3个顶点,但是,看看顶点6,如果它没有5-我们完成了,因为这个图没有连接,就像你在评论中说的那样。

现在让我们看看8,假设它在U'中,因为5不在U'中,所以没有可能的解决方案,在其中,子集U'将被连接。

contradiction

推荐文章

Bala Ji · 以下BFS的实施效率如何?

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

NeoExceptCodeBad · 如果我有很多垂直线,我如何找到它们的边缘?

2 年前

VIAGC · 使用相邻列表创建图形

2 年前

Alexander · 提取节点属性最大值的键

2 年前

R3FL3CT · 如何在Python中将一组网站及其链接转换为有向图?

2 年前

Szyszka947 · 我什么时候可以假设Dijkstra算法中的某个顶点已经完成了最短路径

2 年前

amonroejj · 实现基于节点的工作流的一般原则,如Unreal、Blender、Alteryx等?

8 年前

quantummidget · 正在查找BFS父关系数组

8 年前