[WIL] DFS & BFS

llama·2022년 3월 27일

WIL

목록 보기

2/4

이번주에 배운것

💡 그래프란, 정점과 정점을 연결하는 간선으로 이루어진 자료구조이고 아래는 그래프의 탐색 방법이다.

DFS (Depth First Search)

깊이 우선 탐색으로, 루트 노드(or 임의의 노드)에서 시작하여 왼쪽이나 오른쪽부터 다음 분기(branch)로 넘어가기전에 해당 분기를 완벽하게(최대한의 깊이로) 탐색하는 방식이다.

최대한 깊이 들어가고, 연결된 인접 노드가 더이상 없다면 이전 노드로 돌아와 다시 탐색하는 방식이다.
모든 노드를 방문하고자 하는 경우 DFS방식을 이용한다.
재귀호출이나 스택을 이용하여 구현할 수 있다.
- 노드의 방문 여부를 검사하지 않는다면 무한루프에 빠질 위험이 있다.
- 스택의 LIFO특징에 의해 자동으로 깊이 우선 탐색이 된다.

DFS 시간 복잡도

인접 리스트로 표현된 그래프 : O(V+E)
인접 행렬로 표현된 그래프 : O(V^2)

DFS 구현

# DFS - 재귀호출 구현
# 방문한 내용이 초기화되지 않게 인자로 넘겨주는 것이다.
def dfs_recursive(start_v, visited):
    visited.append(start_v)

    for adj in graph[start_v]:
        if adj not in visited:
            # 해당 재귀호출에서 업데이트된 visited를 다시 인자로 넘겨준다.
            dfs_recursive(adj, visited)

    return visited
# [1, 2, 5, 6, 7, 3, 4] 재귀호출 결과
    
    
# DFS - 스택으로 구현
def dfs_stack(start_v):
    visited = []
    # 방문할 순서를 담아두는 용도
    stack = [start_v]

    while stack:
        # 제일 최근에 삽입된 노드를 꺼내고 방문처리 한다.
        top_v = stack.pop()
        visited.append(top_v)

        # 인접 노드가 visited에 stack에 쌓고 계속 반복문이 돌게 만들어준다.
        for adj in graph[top_v]:
            if adj not in visited:
                stack.append(adj)

    return visited
# [1, 4, 3, 5, 7, 6, 2] 스택 결과

BFS (Breadth First Search)

너비 우선 탐색으로, 루트 노드(or 임의의 노드)에서 시작하여 현재 정점에 인접한 노드를 먼저 탐색하는 방식이다.

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을때 BFS방식을 이용한다.
큐를 이용하여 구현할 수 있다.
- 노드의 방문 여부를 검사하지 않는다면 무한루프에 빠질 위험이 있다.
- 큐의 FIFO특징에 의해 자동으로 너비 우선 탐색이 된다.

BFS 시간 복잡도

인접 리스트로 표현된 그래프 : O(V+E)
인접 행렬로 표현된 그래프 : O(V^2)

BFS 구현

from collections import deque

# BFS - deque를 이용하여 큐로 구현
def bfs_queue(start):
	# 시작 노드를 방문 처리한다.
    visited = [start]
    # 큐를 만들고 시작 노드를 담아준다.
    q = deque([start])

	# 큐가 빌 때까지 반복된다.
    while q:
        node = q.popleft()
        for adj in graph[node]:
        	# 인접 노드가 방문하지 않은곳이라면, 방문 처리와 큐에 쌓아준다.
            if adj not in visited:
                q.append(adj)
                visited.append(adj)
    return  visited

# [1, 2, 3, 4, 5, 6, 7] BFS 결과물이다.