UNION-FIND或DFS：哪一个更适合查找连接组件？ [英] Union-Find or DFS: which one is better to find connected component?

问题描述

UNION-FIND和DFS均可用于查找连接性。哪种情况下哪种更好？

推荐答案

联合查找算法最适合等价关系发生变化的情况，即需要对您的分区集执行"联合"操作。给出一个固定的无向图，等价关系根本不会改变--边都是固定的。OTOH，如果你有一个添加了新边的图，DFS不会剪切它。虽然DFS的速度比Union-Find快得多，但在实践中，可能的决定因素是您试图解决的实际问题。

tl；DR-静态图？DFS！动态图？Union-Find！

这篇关于UNION-FIND或DFS：哪一个更适合查找连接组件？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！