我有一个邻接矩阵nxn。图的每个节点都有m传出边，我想将这些节点分配到b桶中。每个桶应至少保持l和最大u节点（uxb> = n）。存储桶内的每个节点应至少有一个到存储桶内另一个节点的传出边缘。
我觉得我错过了解决这个问题的最佳角度。你会怎么做？
首先将图形分离为连接的组件，这可以通过执行深度优先或广度优先搜索在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
然后删除最终的1度顶点及其邻居：
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
然后整个连接的组件将需要进入同一个桶，因为您不能通过移除一对相邻顶点的三元组来分割图形，而不会保留单个不相交的顶点。您可以通过测试是否删除一对，检查是否有其他相邻的顶点是1级，如果是，则将它们添加到对中。