Summary
•
BFS (Breadth-First Search)
Description
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.
1.
탐색 시작 노드를 큐에 삽입하고 방문 처리를 함
2.
큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드들을 큐에 삽입하고 방문 처리를 함
3.
2의 과정을 더이상 반복할 수 없을 때까지 반복
bfs는 가까운 노드부터 탐색하므로, 모든 간선의 비용이 1인 그래프에서 bfs를 사용하면 최단 거리를 계산할 수 있음.
Data Structure
•
Queue
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
복사
