[python] DFS & BFS

# 그래프

- 노드(정점)와 간선으로 표현

 

 

# DFS

- 깊이 우선 탐색

- 스택

- 그래프의 깊은 부부을 우선적으로 탐색

# dfs 함수
def dfs(graph, v, visisted):
    # 현재 노드 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 노드 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
            
# 각 노드가 연결된 정보를 리스트 자료형으로 표현
graph = [
    [], 
    [2, 3, 8], # 노드 1에 연결된 정보
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]


visited = [False] * 9

dfs(graph, 1, visited)

 

 

 

# BFS

- 너비 우선 탐색

- 가까운 노드부터 탐색

- 큐

from collections import deque

# bfs 함수
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 visited[i]:
                queue.append(i)
                visited[i] = True
    
    
# 각 노드가 연결된 정보를 리스트 자료형으로 표현
graph = [
    [], 
    [2, 3, 8], # 노드 1에 연결된 정보
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]


visited = [False] * 9

bfs(graph, 1, visited)