我需要一种算法来查找大图的 k 大小子图。你的建议是什么？
注意：我的图表是无向的。
提前致谢。
问问题
964 次
2 回答
0
如果你从一个大图中选择任何 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
于 2012-06-17T15:41:35.053 回答