DFS,BFS

DFS, BFS 둘 다 그래프를 탐색하는 방법이다

DFS 깊이 우선 탐색 (Depth-First Search)

• 현재 정점에서 갈 수 있는 점들까지 들어가며 탐색
• 스택 또는 재귀함수로 구현
• 경로의 특징을 저장해야하는 문제에 사용

구현(재귀)

def dfs(graph, v, visited):
	visited[v] = True
    print(v,end=' ')
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
            
visited = [False] *len(graph)

dfs(graph, 1, visited)

BFS 너비 우선 탐색 (Breadth-First Search)

• 현재 정점에 연결된 가까운 점들부터 탐색
• 큐로 구현
• 최단거리 문제에 사용

구현

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    
    while queue:
    	v = queue.popleft()
        print(v, end = ' ')
        
        for i in graph[v]:
        	if not visted[i]:
            	queue.append(i)
                visited[i] = True
                
visited = [False] *len(graph)

bfs(graph, 1, visited)