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

将图节点分配到桶中

graph-algorithm graph-theory algorithm

0

tcurdt · 技术社区 · 7 年前

我有一个邻接矩阵 n 十 不 m 我想把这些节点分布到 b 每个铲斗应至少容纳 l 最大值为 u 节点( u型 &燃气轮机= 不 ). bucket内的每个节点都应该至少有一条到bucket内另一个节点的传出边。

我觉得我错过了解决这个问题的最佳角度。你将如何处理这个问题?

1 回复 | 直到 7 年前

1

MT0 7 年前

首先,将图形分割成连接的组件,这可以通过执行深度优先或广度优先搜索在O(n)时间和内存中完成。

如果任何节点未连接到另一个节点,则解决方案是不可能的。

从每个DFS/BFS树的叶子(即仅连接到另一个节点的节点)开始,将每个连接的组件拆分为相邻节点的成对(或三元组)。每一对(或三元组)都应该进入下一个存储桶,其中的节点数最少。

      o   o
     / \  |
o   o   o o     |    |    |    |    |    |
|  / \ /  |     |    |    |    |    |    |
o o   o   o     |    |    |    |    |    |
 \ \ /   /      |____|    |____|    |____|
  --o----      Bucket 1  Bucket 2  Bucket 3

从左叶删除2个节点。

      o   o
     / \  |
a   o   o o     |a   |    |    |    |    |
|  / \ /  |     ||   |    |    |    |    |
a o   o   o     |a   |    |    |    |    |
 \ \ /   /      |____|    |____|    |____|
  --o----      Bucket 1  Bucket 2  Bucket 3

从右叶删除2个节点。

      o   b
     / \  |
    o   o b     |a   |    |b   |    |    |
   / \ /  |     ||   |    ||   |    |    |
  o   o   o     |a   |    |b   |    |    |
   \ /   /      |____|    |____|    |____|
    o----      Bucket 1  Bucket 2  Bucket 3

      o    
     / \   
    o   o       |a   |    |b   |    |c   |
   / \ /        ||   |    ||   |    ||   |
  o   o   c     |a   |    |b   |    |c   |
   \ /   /      |____|    |____|    |____|
    c----      Bucket 1  Bucket 2  Bucket 3

这将在剩余子图中创建一个新的1阶顶点,以便删除该顶点及其相邻顶点:

      o    
     / \   
    d   o       |a d |    |b   |    |c   |
   / \ /        || | |    ||   |    ||   |
  d   o         |a d |    |b   |    |c   |
                |____|    |____|    |____|
               Bucket 1  Bucket 2  Bucket 3

只剩下3个顶点,如果它能放进一个桶里,那么就把它放进桶里——否则就把一对从物品数量最少的桶里移到物品数量次之的桶里,然后把三元组加进去。

      e    
       \   
        e       |a d |    |e e |    |c b |
       /        || | |    |\ / |    || | |
      e         |a d |    | e  |    |c b |
                |____|    |____|    |____|
               Bucket 1  Bucket 2  Bucket 3

唯一的问题将是当你得到星形连接组件

  o   o
   \ /
 o--o--o
   / \
  o   o