DFS와 BFS

DFS와 BFS란?

BFS, DFS 두가지 모두 그래프를 탐색하는 방법이다.

그래프란?

정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 말한다.
그래프를 탐색한다는 것은 임의의 노드에서부터 시작해 모든 정점들을 한 번씩 방문하는 것을 말한다.

DFS (깊이 우선 탐색)

루트 노드(혹은 다른 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

BFS (너비 우선 탐색)

루트 노드(혹은 다른 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 노드로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

구현

변수선언

# popleft 사용을 위한 deque선언
from collections import deque

# 정점 개수, 간선 개수, 탐색시작 정점번호
n, m, v = map(int, input().split())

# 그래프(크기, 개수: 정점개수+1만큼)
graph = [[0]*(n+1) for i in range(n+1)]

# 방문한 곳 체크
visit1 = [0] * (n+1)  # dfs의 방문표시
visit2 = [0] * (n+1)  # bfs의 방문표시

# 입력 받는 두 값의 열행렬에 1 삽입
for i in range(m):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1

dfs

# 깊이 우선 탐색
def dfs(v):

    # 방문한 곳 1 넣고 출력
    visit1[v] = 1
    print(v, end=' ')

    # 1~정점개수 만큼 반복
    for i in range(1, n+1):
        # v와 인접한 곳 찾고 방문하지 않았다면 함수 다시 실행
        if visit1[i] == 0 and graph[v][i] == 1:
            dfs(i)

bfs

# 넓이우선 탐색
def bfs(v):

    # deque선언 후 탐색번호 넣기
    q = deque()
    q.append(v)

    # 탐색표시
    visit2[v] = 1

    # q가 텅빌 때까지
    while q:

        # 탐색번호를 q[-1]로 설정 후 그 값 q에서 삭제
        v = q.popleft()
        print(v, end=' ')

        # 1~정점개수 만큼 반복
        for i in range(1, n+1):
            # v와 인접한 곳 찾고 방문하지 않았다면
            if visit2[i] == 0 and graph[i][v] == 1:
                # 큐에 정점번호 추가 후
                q.append(i)
                # 방문표시
                visit2[i] = 1