DFS (깊이 우선탐색)
- 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요함.
- 두 가지 방법
- 깊이 우선 탐색
- 너비 우선 탐색
- 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면,
가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여
결국 모든 정점을 방문하는 순회방법 - 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용
DFS 알고리즘 (수도코드)
visited[], stack[] 초기화
DFS(v)
시작점 v 방문;
visited[v] <- ture:
while{
if (v의 인접 정점 중 방문 안 한 정점 w가 있으면)
push(v);
v <- w; (w에 방문)
visited[w] <- ture;
else
if (스택이 비어있지 않으면)
v <- pop(stack);
else
break
}
end DFS()
DFS 예
- 초기상태 : 배열 visited를 False로 초기화하고, 공백 스택을 생성
1) 정점 A를 시작으로 깊이 우선 탐색을 시작
A 방문;
visited[A] <- true;
2) 정점 A에 방문하지 않은 정점 B, C가 있으므로 A를 스택에 push 하고,
인접정점 B와 C 중에서 오름차순에 따라 B를 선택하여 탐색을 계속한다.
push(A);
B 방문;
visited[B] <- true;
3) 정점 B에 방문하지 않은 정점 D,E가 있으므로 B를 스택에 push 하고, 인접정점 D와 E 중에서 오름차순에 따라
D를 선택하여 탐색을 계속한다.
push(B);
D 방문;
visited[D] <- true;
4) 정점 D에 방문하지 않은 정점 F가 있으므로 D를 스택에 push 하고, 인접정점 F를 선택하여 탐색을 계속한다.
push(D);
F 방문;
visited[F] <- true;
5) 정점 F에 방문하지 않은 정점 E, G가 있으므로 F를 스택에 push 하고, 인접정점 E와 G중에서 오름차순에 따라
E를 선택하여 탐색을 계속한다.
push(F);
E 방문;
visited[E] <- true;
6) 정점 E에 방문하지 않은 정점 C가 있으므로 E를 스택에 push 하고, 인접정점 C를 선택하여 탐색을 계속한다.
push(E);
C 방문;
visited[C] <- true;
7) 정점 C에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop 하여 받은 정점 E에 대해서 방문하지 않은 인접정점이 있는지 확인한다.
pop(stack);
8) 정점 E는 방문하지 않은 인접정점이 없으므로, 다시 스택을 pop하여 받은 정점 F에 대해서 방문하지 않은
인접정점이 있는지 확인한다.
pop(stack);
9) 정점 F에 방문하지 않은 정점 G가 있으므로 F를 스택에 push 하고, 인접정점 G를 선택하여 탐색을 계속한다.
push(F);
G 방문;
visited[G] <- true;
10) 정점 G에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop하여 받은
정점 F에 대해서 방문하지 않은 인접정점이 있는지 확인한다.
pop(stack);
11) 정점 F에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop하여 받은
정점 D에 대해서 방문하지 않은 인접정점이 있는지 확인한다.
pop(stack);
12) 정점 D에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop하여 받은
정점 B에 대해서 방문하지 않은 인접정점이 있는지 확인한다.
pop(stack);
13) 정점 B에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop하여 받은
정점 A에 대해서 방문하지 않은 인접정점이 있는지 확인한다.
pop(stack);
14) 현재 정점 A에서 방문하지 않은 인접정점이 없으므로, 마지막 정점으로 돌아가기 위해 스택을 pop하는데,
스택이 공백이므로 깊이 우선 탐색을 종료한다.
깊이 우선 탐색 경로 : A - B - D - F - E - C - G
<연습문제3>
- 다음은 연결되어 있는 두 개의 정점 사이의 간선을 순서대로 나열해 놓은 것이다.
모든 정점을 깊이 우선 탐색하여 화면에 깊이 우선 탐색 경로를 출력하시오.
시작 정점을 1로 시작하시오.
[코드]
'''
1
7 8
1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7
'''
def DFS(s, V): # s: 시작정점, V: 정점 개수 (1번부터인 정점의 마지막 정점)
visited = [0]*(V+1) # 방문한 정점을 표시
stack = [] # 스택 생성
print(s)
visited[s] = 1 # 시작정점 방문 표시
v = s # 현재 정점 : v
while True:
for w in adjL[v]: # v에 인접하고, 방문안한 w가 있으면
if visited[w] == 0:
stack.append(v) # push(v) 현재 정점을 push하고
v = w # w에 방문
print(v)
visited[w] = 1 # w에 방문표시
break # for w, / 남은 갈림길을 두고 v
else: # 남은 인접정점이 없어서 break가 걸리지 않은 경우
if stack: # 이전 갈림길을 스택에서 꺼내서... if TOP > -
v = stack.pop()
else: # 되돌아갈 곳이 없으면 / 남은 갈림길이 없으면 탐색 종료
break # while true: 에 대한 break
T = int(input())
for tc in range(1, T+1):
V, E = map(int, input().split())
adjL = [[] for _ in range(V+1)]
arr = list(map(int, input().split()))
for i in range(E):
v1, v2 = arr[i*2] , arr[i*2+1]
adjL[v1].append(v2)
adjL[v2].append(v1)
DFS(1, V)