Какой подход лучше всего использовать Bfs, Dfs или Disjoint для поиска всех несвязных графов?

Question

Какой подход лучше всего использовать Bfs, Dfs или Disjoint для поиска всех несвязных графов?

Какой подход мы должны использовать, чтобы найти все несвязные графы и почему?

Как обходы BFS и DFS, так и методы обхода, и путем нескольких обходов. Мы можем найти все отключенные компоненты.
И другим подходом может быть " Непересекающиеся множества", используемые в kruskal (MST) для поиска отключенных компонентов.

1

depth-first-search breadth-first-search disjoint-sets disjoint-union

Источник

user7473687 18 окт '17 в 11:11

1 ответ

Другие вопросы по тегам depth-first-search breadth-first-search disjoint-sets disjoint-union

user6468580 20 окт '17 в 10:16 2017-10-20 10:16 · Answer 1 · 2017-10-20 10:16

Просто потому, что вы заявили, что вам нужно найти все отключенные графики, я бы порекомендовал использовать BFS, поскольку он завершен, поиск в глубину - нет. При применении к бесконечным графам, представленным неявно, BFS найдет целевое состояние, в вашем сценарии найдет все отключенные графы. DFS, с другой стороны, может потеряться в тех частях графика, которые не содержат состояния цели, и, по сути, может потеряться.