[이코테 # DFS/BFS 1] DFS, BFS 예제

* DFS(Depth-First Search, 깊이 우선 탐색)

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
• 선입후출. 스택(재귀 함수) 사용
• 관행적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다.

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 = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3,4],
    [7],
    [2, 6, 8],
    [1,7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False]*9

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

 

 

* BFS(Bredth First Search 너비 우선 탐색)

• 가까운 노드부터 탐색하는 알고리즘.
• 선입 선출. 큐(queue) 사용

from collections import deque


def bfs(graph, start, visited):
    # Queue 구현을 위해 deque 라이브러리 사용
    queue = deque([start])	# deque 안에는 리스트나 튜플이 들어가야 한다.
    # 현재 노드를 방문 처리
    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, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
bfs(graph, 1, visited)

* deque([1,2,3])을 하면 [1,2,3]이 생기고 여기서 append([4,5])을 하면 [1,2,3,[4,5]]가 된다. deque([[1,2,3]])은 [[1,2,3]]을 생성한다.