Я предполагаю, что это два отдельных вопроса.
Union-Find
Теоретическая сложность алгоритма
Сложность Union-Find составляет O (logn), когда используется сжатие пути, и O (n), если оно не используется. Строгое подтверждение этого может быть больше, чем вы искали, но их можно найти в inte rnet.
Applications
Union-Find is используется в алгоритме Крускала для поиска минимального остовного дерева. Алгоритм объединения-поиска используется для отслеживания непересекающихся минимальных остовных деревьев (классов эквивалентности), сформированных на промежуточных этапах Крускала. Это моя единственная встреча с алгоритмом. На inte rnet можно найти другие приложения, такие как:
https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Applications
Поиск в ширину
Сложность теоретического алгоритма
Временная сложность BFS равна O (V + E), где V - количество вершин, а E - количество ребер. Для полных графов временную сложность можно представить как O (V ^ 2). Для разреженных графов временная сложность может рассматриваться как O (V). Сложность времени обусловлена тем фактом, что каждая вершина исследуется только один раз, а каждое ребро исследуется дважды в худшем случае в неориентированном графе (или один раз в ориентированном графе).
Приложения
Мои встречи с BFS были в таких местах, как нахождение минимального остовного дерева невзвешенного графа, нахождение кратчайшего пути к узлу во невзвешенном графе (BFS не работает для взвешенных графов, где кратчайший путь не является равно минимальному количеству ребер между ними). Другое использование для BFS - это обход уровня дерева. Еще много примеров применения можно найти здесь:
https://www.geeksforgeeks.org/applications-of-breadth-first-traversal/