DFS & BFS

유진·2023년 1월 25일

BFS DFS Graph algorithm

모각소 2주차

DFS (Depth First Search)

깊이 우선 탐색

응용

위상정렬 (ex. 선수과목 정렬)
중위순회 (In-order traversal of BST)
Finding connected components (기준점에서 닿을 수 있는 모든 node 찾기)

3종류의 node state

Unvisited : 아직 방문하지 않음
In progress : 현재 node를 방문 O, 연결된 모든 node 방문 X
All done : 현재 node를 방문 O, 연결된 모든 node 방문 O

→ 현재 node가 All done이면, 이전 node로 return

→ 시작 node가 All done이면, 탐색 종료

구현방법

순환호출
명시적 stack 사용 (방문한 node push, pop)

CODE

import sys

# 현재 node와 연결된 모든 node가 visited O -> return 이전 node
# 현재 node와 연결된 모든 node가 visited X -> 연결된 node 중 가장 작은 node로 이동
def DFS(startNode):
    visited[startNode] = True
    print(startNode, end=" ")
    for i in matrix[startNode]:
        if(not visited[i]):
            DFS(i)
            
node, edge, start = map(int, sys.stdin.readline().split())

# Graph에서 node끼리 connection 확인
matrix = [[] for i in range(node+1)]

# 방문 여부 저장
visited = [False]*(node+1)

# Graph 형성
for i in range(edge):
    n1, n2 = map(int, sys.stdin.readline().split())
    matrix[n1].append(n2)
    matrix[n2].append(n1)

for i in range(1, node+1):
    matrix[i].sort()
    
for i in range(1, node+1):
    print(matrix[i])
    
DFS(start)

BFS (Breadth First Search)

너비 우선 탐색

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색
깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.

응용

두 node 사이의 최단 경로 찾기 / 임의의 경로 찾기

특징

재귀 X
어떤 노드를 방문했는지 반드시 검사 → 무한 루프에 빠지지 않도록 !
‘Prim’, ‘Dijkstra’ 알고리즘과 유사

구현방법

Queue 사용 (FIFO)

CODE

from collections import deque

def BFS(node, graph, visited):
    q = deque()
    q.append(node)
    visited[node] = True
    
    while q:
        v = q.popleft()        
        print(v, end=" ")

        for i in graph[v]:
            if (visited[i]==False):
                q.append(i)
                visited[i] = True

nodeNum, edgeNum, startNode = map(int, input().split())

visited = [False]*(nodeNum+1)
graph = [[] for _ in range(nodeNum+1)]

for i in range(edgeNum):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)
    
for i in range(nodeNum):
    graph[i].sort()
BFS(startNode, graph, visited)