Pra*_*han 16
union-find算法最适合等价关系发生变化的情况,即需要在您的分区集上执行"Union"操作.给定一个固定的无向图,你根本没有改变等价关系 - 边都是固定的.OTOH,如果您有一个添加了新边的图表,DFS将不会删除它.虽然DFS渐近比union-find快,但在实践中,可能的决定因素将是您试图解决的实际问题.
tl; dr - 静态图？DFS!动态图？联盟找到!
如果图形已经以邻接列表格式存在于内存中,则DFS稍微简单且更快(O(n)对O(n alpha(n)),其中alpha(n)是逆Ackermann),但是union-find可以处理边缘以任何顺序在线到达,这有时是有用的(例如,有太多不适合主存储器).
小智 8
如果图已经以邻接列表或矩阵的形式给出，那么 DFS/BFS 更合适，但如果给出边/关系列表，那么更适合使用 DSU（不相交集），就好像你会去为了从边制作图表，首先您将制作图表，然后进行 dfs，但通过形成 dsu，您可以直接计算组件的数量以及每个组件中的节点/边的数量。