나는 수를 세는 방법을 찾았다. 연결된 구성 요소 온라인. 대부분의 사이트에서 사용 된 알고리즘은 심도 우선 검색입니다. 나는 당신이 똑같은 것을 성취 할 수 있다고 믿습니다. 처음으로 수색과 노동 조합도 발견합니다. 그렇다면 왜 사람들은 연결된 구성 요소의 수를 찾기 위해 DFS를 선호합니까? 주로 두 가지 이유로다른 알고리즘과 비교할 때, 깊이 우선 탐색은 그래프에서 연결된 구성 요소의 수를 계산하기위한 더 나은 솔루션이됩니까?
:
O(V) (V은 노드 수)입니다. 반면에 DFS는 O(h) (h은 재귀 트리의 최대 깊이 임)입니다.데이터 구조가 필요 없다는 말입니다. 그러나 DFS 구현에서 정점에 의해 인덱싱 된 부울 배열이있는 것을 보았습니다. 배열의 목적은 순회 중에 각 꼭지점을 "방문한"것으로 표시하는 것이 었습니다. 따라서 배열이 "visited"라고 불리면 vertex 5가 방문되면 visited [5]가 true로 설정됩니다. – Viktorja
DFS가 배열을 데이터 구조로만 사용한다는 것을 의미하지만 다른 알고리즘은 더 많은 데이터 구조를 사용하므로 DFS가 간단 해집니다. 이것이 DFS의 메모리 복잡성을 개선하는 데 기여하는 것입니까? – Viktorja
예. DFS는 노드 N에서 한 번에 스택의 'N'이웃 중 하나만 저장하는 반면, BFS는 'N'의 모든 이웃을 즉시 큐에 넣습니다. – Anonta
모든 경우에서 정확히 한 번만 방문하기 때문에 복잡성 측면에서는 좋지 않습니다. 메모리 사용 측면에서 어떤 노드가 방문되었고 어떤 노드가 발견되었고 아직 방문하지 않았는지를 항상 알아야합니다. 깊이 우선은 자식 노드를 가져와 형제가되기 전에 자손을 방문합니다. 처음에는 자손이 먼저 자손을 방문합니다. 깊이 우선은 짧고 단순하고 틀림없이 더 직관적인데, 이는 다른 사람들보다 자습서, 서적 및 프리젠 테이션에서 더 자주 선택되는 이유 일 수 있습니다.
많은 경우에 사용되는 스택은 재귀에 의해 처리되지만, 특히 큰 그래프의 경우에는 반드시 좋은 생각은 아닙니다.
경쟁 프로그래밍 리소스를 연구하고있는 것 같습니다. 거기에 단순함이 있고 DFS는 일반적으로 코드가 적습니다. 실제 시나리오에서는 최상의 솔루션이 아닐 수도 있습니다. –