DFS와 BFS

DFS와 BFS 정리

DFS (stack이용)

1. stack에 첫 노드 넣고 방문 표시
2. 인접한 노드 중 방문하지 않은 노드 탐색
   더 이상 없다면 stack에서 최상단 노드 꺼내기
3. 해당 과정 수행할 수 없을 때까지 반복

# n개의 노드 m개의 간선
graph = [ [], [2,3,8] ,[1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ]
visited = [False] * (n+1)

def DFS( graph, v, visited) :
	visited[v] = True
    
    print(v, end=" ")
    
    for i in range(graph[v]) :
    	if not visited[i] :
    		DFS(graph, i, visited)
                       

BFS (queue이용)

1. queue에 첫 노드 넣고, 방문 표시
2. queue에서 노드 하나 꺼내고, 인접한 노드 + 방문하지 않은 노드들 모두 queue에 삽입
3. 해당 과정 수행할 수 없을 때까지 반복

from collections import deque

# n개의 노드 m개의 간선
graph = [ [], [2,3,8] ,[1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ]
visited = [False] * (n+1)

def BFS( graph, v, visited) :
	q = deque([v])
   	visited[v] = True
    
    while q : # queue가 비어있을 때 까지 반복
    	pop_v = q.popleft()
        print(pop_v, end=" ")
        
        for i in graph[pop_v] :
    		if not visited[i] :
            	q.append(i)
                visited[i] = True