问题背景:
在我女儿学校的每个新年伊始，校长总是说要给 children 分类是多么困难，因为他们有很多关于想和谁一起类的要求，而且幼儿园也有一些建议。
在我看来，这只是一个加权的循环图，以 child 为节点，以请求/推荐为边，需要拆分。
问题:
想象一下，如果你愿意的话，一个带有循环和加权边的图，可能是断开的。 我想将该图划分为 n 个较小的图，每个图至少有 s 个节点，每个图中最多有 t 个节点，同时尽可能少地断开边。 我假设它是 NP 难以解决，所以它可能真的是一个优化问题。
- 这个图算法有名字吗？
- 是否有任何 java 库可以帮助我解决这个问题？
谢谢， 杰斯珀
最佳答案
图的一个组成部分也是一个图。去年我不得不编写图像拼接代码，它使用了具有 64000 像素的有向图数据结构，而且速度一点也不慢。 
生成的图像是最后一张，代码在这里github .
好吧，在您的情况下，您可以创建图形数据结构。创建一个链表的一维数组，并在该链表中保存与三个参数连接的数据结构，第一个是您的第一个学生，第二个是第一个连接到的学生，第三个是表示它们之间强度界限的数字。 :示例学生 1 连接到学生 5，强度 == 100 然后创建一个新节点 Connected c = new connected(1,5,100); 并将其添加到数组的第一个条目，如下所示: array[i].add(c) 其中 i == 1。
搜索:哪个学生连接到哪个学生:当您尝试查找哪个学生连接到哪个学生时，您只需像这样访问数组索引:
`for(Connected c : array[i].get();
int firstStudent = c.getFirst()
int secondStudent = c.getSecond()
int strength = c.getStrength();`
你的链表应该有一个迭代器，这样你就可以遍历。
实际情况是这样的:
关于java - 如何将一个带权循环图分成n个图，尽可能少的断开连接，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47069140/