Computer ScienceAlgorithmTheory

19. 그래프 깊이우선탐색(DFS)

깊이우선탐색(DFS)

현재 방문중인 노드와 연결된 이웃 노드 중 아직 방문하지 않은 노드 있으면, 그 노드를 다음에 방문.
재귀함수로 작성, 마치 트리의 preorder방식과 비슷.

psuedo code

1
2
3
4
5
6
7
8
9
10
DFS(v):
    mark v as visited node
    pre[v] = curr_time #pre리스트는 해당 노드에 첫 방문시각 기록
    curr_time += 1
    for each edge (v, w):
        if w is unmarked:
            parent[w] = v #parent리스트는 해당 노드에 접근 직전에 방문했던 노드 기록
            DFS(w)
    post[v] = curr_time #post리스트는 해당 노드의 이웃이 모두 방문됐을 때 시간 기록
    curr_time += 1

DFS 트리

방문순서를 부모-자식 관계로 나타낸 트리.

왼쪽 트리에 나타난 실선 화살표를 트리 에지라 하고, 오른쪽 트리에 나온 점선 화살표를 백 에지라고 부른다.
즉 DFS의 에지는 트리 에지와 백 에지 두 종류로 나뉘고, 백 에지가 존재함은 사이클이 존재함을 의미한다.

python 코드

노드 갯수와 엣지 갯수 입력 후,
엣지를 입력 받았을 때.

방문한 노드를 순서대로 출력하고,
[pre, post] 쌍을 출력한다.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
def DFS(G, v):
	global curr_time # pre, post를 위한 time stamp
	# 그래프 G의 노드 v를 DFS 방문한다
	visited[v] = True
	pre[v] = curr_time
	curr_time += 1
	neighbor = []
	for i in G:
		if v in i:
			if i[0] == v and visited[i[1]] == False:
				neighbor.append(i[1])
			elif i[1] == v and visited[i[0]] == False: 
				neighbor.append(i[0])
	neighbor.sort()
	for j in neighbor:
		if visited[j] == False:
			parent[j] = v
			DFS(G, j)
			
	post[v] = curr_time
	curr_time += 1
def DFSAll(G):
	# 그래프 G를 DFS 방문한다
	for v in range(n):
		if visited[v] == False:
			DFS(G, v)

# 입력 처리
n, m = [int(x) for x in input().split()]
G = [[] for _ in range(n)]
# G 입력 받아 처리
for _ in range(m):
	x = list(map(int, input().split(' ')))
	G.append(x)
# visited, pre, post 리스트 정의와 초기화
visited = [0]*n
pre = [1]*n
post = [1]*n
parent = [0]*n
# curr_time = 1로 초기화
curr_time = 1

DFSAll(G)

# 출력
result = []
for i in range(n):
	result.append([pre[i], post[i]])
for p in range(len(pre)):
	minIndex = pre.index(min(pre))
	print(minIndex, end=' ')
	pre[minIndex] = max(pre)+1
print()
for k in result:
	print(k, end=' ')
Share