[파이썬/python] DFS, BFS 구현 (재귀)

DFS

def dfs(graph, v, visited):
	#현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visitied[i]:
        	dfs(graph, i, visited)
            

graph = [
	[],
    [2, 3],
    [1],
    [1, 4],
    [3]
  ]

# 각 노드가 방문된 정보를 표현
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visitied)
   

 

BFS

from collections import deque

def bfs(graph, start, visited):
	# 큐 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft()
        print(v, end = ' ')
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
                
                

graph = [
	[],
    [2, 3],
    [1],
    [1, 4],
    [3]
   ]

visited = [False] * 5

bfs(graph, 1, visited)