xan*_*xan 5 algorithm graph graph-algorithm data-structures
我正在练习解决空闲时间的编程问题.我前段时间发现这个问题但仍然不知道如何解决它:
对于具有n个顶点和m个边(小于2×10 6)的给定无向图,我需要将其顶点分成尽可能多的组,但是有一个条件:来自不同组的每对顶点通过边连接.每个顶点恰好在一个组中.最后,我需要知道每个组的大小.
当我提出这个解决方案时,我感到很自豪:考虑原始图的补充图并使用Disjoint-set数据结构.它给了我们正确的答案(不难证明).但这只是理论上的解决方案.在给定的约束下,它非常非常糟糕,不是最优的.但我相信这种方法可以巧妙地修复.但是怎么样？
有人可以帮忙吗？
编辑:对于顶点为1到7和16个边的图:
1 3
1 4
1 5
2 3
3 4
4 5
4 7
4 6
5 6
6 7
2 4
2 7
2 5
3 5
3 7
1 7
我们有3组大小:1,2和4.
这些组分别为:{4},{5,7},{1,2,3,6}.有连接不同组的每对顶点的边,我们无法创建更多组.
我认为您缺少的唯一要素是如何处理稀疏图。
让我们考虑一下寻找最大可能的完整图，其中我能做的唯一操作是将一组节点（例如 v_1，...，v_k）分组在一起，并仅将新的超级节点边赋予那些u连接的节点到所有v_1, ..., v_k。
如果您的图的边少于 n^2/4，请随机采样n节点对，并注意哪些对没有由边连接。Union-find 是一种简单的编码方法。现在，使用通过此随机采样找到的集合作为组来重建图表。递归这个简化图。（我不太确定如何分析此步骤，但我相信每个样本重建周期都会以高概率将图形大小至少减少一个常数因子，因此整个过程需要接近线性的时间。）
一旦你有了一个相当密集的图（至少 n^2/4 条边），你就可以转换为邻接矩阵表示并完全按照你的建议去做——检查所有节点对，每当你看到两个节点时就进行并集没有由边连接，并读出集合。