Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- GIT
- 2021 KAKAO BLIND RECRUITMENT
- SWEA
- 프로그래머스
- Spring
- 투포인터
- 우선순위큐
- 스택
- 백트래킹
- 파이썬
- 비트마스킹
- 플로이드 와샬
- 백준
- 이분탐색
- 트라이
- 2019 KAKAO BLIND RECRUITMENT
- 2020 KAKAO BLIND RECRUITMENT
- 다익스트라
- BFS
- 플로이드와샬
- 최소 신장 트리
- 투 포인터
- 크루스칼
- 2020 카카오 인턴십
- 시뮬레이션
- 브루트포스
- 2018 KAKAO BLIND RECRUITMENT
- 구현
- 조합
- 로봇 청소기
Archives
- Today
- Total
개발조아
그래프 탐색 본문
728x90
- 깊이 우선 탐색(Depth First Search : DFS)
- 한 정점으로부터 연결된 한 정점으로만 탐색하여 끝까지 탐색하는 방법
- 한 정점에서 연결된 정점을 찾아 해당 정점으로 이동
- 만약 연결된 정점이 없다면 이전 정점으로 이동해 다른 정점 탐색
- 모든 정점에 대해서 탐색이 이루어진다
- 구현 방법
- Stack
- 현재 정점에 연결된 다른 정점을 찾을 시 돌아갈 정점, 즉 현재 정점을 스택에 저장
- 현재 정점에서 연결할 정점이 없어면 스택에서 다시 정점을 빼서 수행
- 재귀로도 구현 가능
- 현재 정점에 연결된 다른 정점이 있다면 다시 재귀 호출
- 현재 정점에서 연결할 정점이 없다면 해당 재귀 탈출
- Stack
- 시간 복잡도
- O(V+E)
- 너비 우선 탐색(Breadth First Search : BFS)
- 한 정점에 연결된 모든 정점을 모두 탐색
- 트리에서의 레벨순회 처럼 현재 정점을 기준으로 연결된 모든 정점을 탐색
- 구현방법
- Queue
- 탐색할 정점을 순서대로 빼기 위해 큐를 사용
- 현재 정점에서 연결된 다른 정점을 큐에 넣는다
- 현재 정점 탐색이 끝나면 큐에서 다음 정점을 빼서 위의 과정을 반복한다
- 큐를 활용하여 먼저 탐색한 순서대로 방문을 하기 때문에 가중치가 1인 그래프에서 최단 거리로 이동이 가능
- Queue
- 시간 복잡도
- O(V+E)
'CS > 알고리즘&자료구조' 카테고리의 다른 글
최소 신장 트리(Minimum Spannig Tree) (0) | 2021.10.20 |
---|---|
그래프의 최단 경로 탐색 (0) | 2021.10.19 |
그래프(Graph) (0) | 2021.10.19 |
힙(Heap) (0) | 2021.10.19 |
이진 탐색 트리(Binary Search Tree) (0) | 2021.10.19 |
Comments