BFS | Graph | DFS 01
그래프
그래프의 DataStructure : 인접행렬 | 인접리스트 | 간선 리스트
- 그래프의 탐색 : DFS | BFS
연결요소개념 : 잘린 파편 그래프 조각을 연결요소(컴포넌트)라고 정의 한다.
- BFS|DFS 를 N번 돌려서 컴포넌트 수 N를 구할 수 있음
이분그래프 : A,B 두 그룹으로 노드를 나눔, 그룹안에 간선은 존재하지 않음
탐색을 통해, check값을 1,2 로 번갈아 주면서 나눌 수 있음.
- 싸이클 찾기 : 순열, 반복 수열 등으로 문제를 wrap함, 1차수의 그래프로 보고 1차원 graph를 만든다음, 컴포넌트를 파악하는 문제.!!
- 플러드 필: graph가 배열 형태의 구조(인접행렬 아님!) -> | 1. 갈수있는지check | 2. 범위 check| 3. 방문여부 check 최소 3단계!
DFS/BFS 시간 복잡도
*가정 : V - 정점 수, E - 간선 수
- 인접 행렬 : V**2 ( 플러드 필 같은 경우도 이에 해당 )
- 인접 리스트 : V+E
DFS의 시간 복잡도
인접행렬인 경우 , V**2 시간이 걸린다.
정점을 방문할때마다(V개) ~ V개의 노드를 탐색하므로
인접리스트인 경우 V + E의 시간이 걸린다.
DFS가 끝났을때는,모든 정점을 방문하고(V), 간선을 한번식 검사하게 되므로 (E)