我需要一个算法来找到一个大图的 k 个大小的子图。你有什么建议?
注意:我的图是无向的。
提前致谢。
最佳答案
如果您从一个大图中选择任意 k 个顶点,您可以通过仅选择这些顶点和连接它们的边(如果有的话)来创建子图。
如果你想连接你的 k 个顶点,你可以从大图的连接组件中选择 k 个连接的顶点 - 参见 http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29
如果你真的想要 k 个顶点,这样每个顶点都有一条边将它连接到其他 k-1 个顶点中的每一个,那么你需要知道这称为 clique,并且发现这是一个难题 - 请参阅 http://en.wikipedia.org/wiki/Clique_%28graph_theory%29
关于algorithm - K 尺寸子图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11072438/