BFS/DFS

 

def BFS(graph, start_node):

	from collections import deque
    visited = {}
    queue = deque([])
    
    queue.append(start_node)
    
    while queue:
    	node = queue.popleft()
        visited[node] = True
        queue.extend(graph[node])
        
    return list(visited.keys())

 

graph가 list형태로 주어지고 BFS알고리즘으로 방문노드를 뽑아낸다.

특히 방문노드는 딕셔너리나 SET으로 추가해주는 것과,

list의 pop(0)보다 deque를 이용하여 popleft를 이용하는것이 시간복잡도 측면에서 이득을 볼 수 있다.

 

 

visited = [False] * 10
graph = [[], ... ,[]]

def DFS(graph, node, visited):
	visited[node] = True
    print(node, end='->')
    
    for n in graph[node]:
    	if not visited[n]:
    		DFS(graph, n, visited)​