[Python] 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

깊이 우선 탐색(DFS)

코드

# 깊이 우선 탐색 dfs
def dfs(graph, v, visited):
    visited[v] = True
    print(v, end= ' ')
    for i in graph[v]:
        if not visited[i]: # 방문하지 않았을 때
            dfs(graph, i, visited)
    
graph = [
    [], # 0번 인덱스는 보통 비워둔다
    [2, 3, 8], # 1번 노드에 인접한 노드들
    [1, 7], # 2번 노드에 인접한 노드들
    [1, 4, 5], # 3번 노드에 인접한 노드들
    [3, 5], # 4번 노드에 인접한 노드들
    [3, 4], # 5번 노드에 인접한 노드들
    [7], # 6번 노드에 인접한 노드들
    [2, 6, 8], # 7번 노드에 인접한 노드들
    [1, 7] # 8번 노드에 인접한 노드들
]

# 각 노드의 방문 여부
visited = [False] * 9

# DFS 함수 호출
dfs(graph, 1, visited)

실행 결과

1 2 7 6 8 3 4 5 

너비 우선 탐색(BFS)

코드

# 너비 우선 탐색 bfs

from collections import deque 

def bfs(graph, start, visited):
    # deque 객체 생성
    queue = deque([start])
    # 노드 방문 처리
    visited[start] = True
    
    # queue가 빌 때까지 반복
    while queue:
        # queue의 최하단 요소를 제거
        v = queue.popleft()
        print(v, end=' ')
        # 아직 방문하지 않은 인접한 요소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]: # 아직 방문하지 않은 경우
                queue.append(i) # 큐에 추가
                visited[i] = True # 방문 표시

graph = [
	[], # 0번 인덱스는 보통 비워둔다
    [2, 3, 8], 
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드의 방문 여부
visited = [False]*9

#BFS함수 호출
bfs(graph, 1, visited)

실행 결과

1 2 3 8 7 4 5 6