- 인접 행렬을 이용한 DFS 구현
a[x][i] 값이 1인지(=연결된 간선이 있는지) 확인하면서 방문한 적이 없는 정점을 방문 해야함.
void dfs(int x) {
check[x] = true;
for(int i = 1; i <= n; i++) {
if (a[x][i] == 1 && check[i] == false) {
dsf(i);
}
}
}
-인접 리스트를 이용한 DFS 구현
인접 행렬을 이용할 때와 달리 연결된 간선을 확인할 필요가 없음. 방문 여부만 확인!
=> 인접 리스트에 이미 연결된 간선만 저장되어 있기 때문이다.
void dfs_list(int x) {
check[x] = true;
for(int i = 0; i < a[x].length(); i++) {
int y = [x][i];
if (check[y] == false) {
dfs(y);
}
}
}
배열 visited를 F로 초기화하고 공백 스택을 생성한다. 방문한 정점은 T로. (=visited)
정점 A에 아직 방문하지 않은 정점 B,C가 있으므로 스택에 A 집어넣고 오름차순에 따라서 B부터 선택해서 탐색.
이때 배열 visited에서 B와 C 모두 차례로 T로 바꾼다.
정점 B에 방문하지 않은 정점 D,E가 있으므로 스택에 B 집어넣고 오름차순 따라서 D부터 선택 후 탐색.
| A | B | C | D | E | F | G |
| T | T | F | T | F | F | F |
정점 D에 아직 방문하지 않은 정점 G가 있으므로 스택에 G 집어넣고 인접정점 G를 선택해서 탐색 계속.
| A | B | C | D | E | F | G |
| T | T | F | T | F | F | T |
정점 G에 아직 방문하지 않은 정점 E와 F 존재, 오름차순 따라서 E 선택 후 탐색
| A | B | C | D | E | F | G |
| T | T | F | T | F | F | T |
정점 E에 아직 방문하지 않은 정점 C 존재, 스택에 E 집어넣고 인접정점 C를 선택해서 탐색 계속.
| A | B | C | D | E | F | G |
| T | T | T | T | T | F | T |
정점 C에서 더 이상 방문하지 않은 인접정점이 존재하지 않는다. 따라서 마지막 정점으로 돌아가기 위해서 스택을 pop하여 받은 정점 E에 대해서 방문하지 않은 인접정점이 있는지 확인. = B, C, G check!
정점 G 스택에서 pop하여 인접정점 확인. F 아직 방문하지 않았으므로 스택에 push 해주기
| A | B | C | D | E | F | G |
| T | T | T | T | T | T | T |
스택이 공백이 될 때까지 탐색. 만약 스택이 공백이면 깊이 우선 탐색 종료하기.
'Major > Data Structure & Algorithm' 카테고리의 다른 글
| [Algorithm] DP (0) | 2022.10.30 |
|---|---|
| Binary Tree (0) | 2022.05.22 |
| 후위식 연산 (0) | 2022.04.22 |
| Stack , 괄호검사(Valid Braces), Infix to Postfix algorithm (0) | 2022.04.16 |
| review (0) | 2022.04.16 |