Summary
•
DFS (Depth-First Search)
Description
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법.
이름 그대로 깊이를 우선적으로 탐색한다. 방문 기록을 하는 것이 특징.
1.
방문 체크 했던 곳인지 체크
2.
(방문 안한 곳이면)방문 체크
3.
다음 노드로 이동
이런 식으로 진행되고 base case로는 노드를 방문하여 다음 노드가 없으면 return 하는 식으로 진행된다. 재귀로 구현하는 것이 일반적이다. 물론 이는 문제마다 다르고, 개개인의 논리마다 다르다.
Data Structure
•
Stack
Time Complexity
정점의 수 : N, 간선의 수 : E
•
인접 리스트로 표현된 그래프 : O(N + E)
•
인접 행렬로 표현된 그래프 : O(N^2)
Code
DFS와 BFS ( c++ 코드는 조만간 업데이트 예정..)
import sys
from collections import deque
dfs_result = []
def dfs(li,visited,V):
dfs_result.append(V)
if len(li[V]) < 1:
return
for i in range(len(li[V])):
if not visited[li[V][i]]:
visited[li[V][i]] = 1
dfs(li,visited,li[V][i])
bfs_result = []
def bfs(li,visited,V):
q = deque()
q.append(V)
visited[V] = 1
while q:
val = q.popleft()
bfs_result.append(val)
for i in range(len(li[val])):
if visited[li[val][i]]:
continue
else:
q.append(li[val][i])
visited[li[val][i]] = 1
N,M,V = map(int,sys.stdin.readline().split())
li = [[] for _ in range(N+1)]
for _ in range(M):
a,b = map(int,sys.stdin.readline().split())
li[a].append(b)
li[b].append(a)
li[a].sort()
li[b].sort()
visited = [0]*(N+1)
visited[V] = 1
dfs(li,visited,V)
visited = [0]*(N+1)
bfs(li,visited,V)
for dfs_ in dfs_result:
print(dfs_, end = ' ')
print()
for bfs_ in bfs_result:
print(bfs_, end = ' ')
Python
복사
