목록시간복잡도 (1)

개발정리

그래프 탐색

그래프의 탐색 이란? 그래프의 모든 정점을 특정한 순서에 따라 방문하는 알고리즘 깊이 우선 탐색과 너비우선 탐색이 있다. 깊이 우선 탐색 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법 현재 정점과 인접한 간선들을 하나씩 검사하다가 아직 검사하지 않은 간선이 있다면 방문 더이상 갈곳없는 막힌 정점에 도달하면 되돌아감 깊이 우선 탐색의 시간 복잡도 인접리스트 이용 for문에 의해 V번 호출 각 정점에서 dfs()가 호출(E번) 따라서 시간복잡도는 O(V+E) 인접행렬 사용 인접행렬은 2차원 배열을 모두 탐색(V*V) 따라서 O(V^2)
알고리즘/개념 2023. 7. 28. 18:34
이전 Prev 1 Next 다음