DFS (Depth First Search) 깊이 우선 탐색 설명

DFS는 우선 제목에 나와있듯이 '탐색'하는 알고리즘입니다.

고로 이는 순서가 있는 혹은 방향이 있는 자료구조에서 쓰이며

이는 선형 자료구조라고 합니다.

 

우선 DFS의 탐색 과정을 봅시다.

위의 사진은 DFS의 작동 순서를 매우 간단히 표현한 그래프입니다.

화살표를 신경쓰기보다는 노드의 숫자를 보시면 좋습니다.

노드의 숫자는 순서를 의미합니다.

 

고로 DFS의 원리를 정리하자면

연결된 노드들 중 하나를 골라 그 노드에서 계속 탐색하고 탐색되지 않은 노드는 따로 처리하는 것입니다.

 

이를 코드로 구현하면 아래처럼 됩니다.

*코드에서는 연결요소(connected component)를 구합니다.

주석 O

n, m = map(int ,input().split()) # n : node, m = 간선
visited = []
graph = {}

# 양방향 그래프일 때만
# 인접 리스트
for i in range(m):
    f, s = map(int ,input().split())
    if not f in graph:
        graph[f] = []
    if not s in graph:
        graph[s] = []
    graph[f].append(s)
    graph[s].append(f)

# DFS 깊이 우선 탐색

def DFS(graph, start, visited):
    visited.append(start)
    print(start, end=' ')

    for neighbor in graph[start]: # 해당 노드의 끝까지 탐색
        if neighbor not in visited:
            DFS(graph, neighbor, visited)

nodes = list(graph.key()) # 그래프 상의 모든 노드를 기록
connected_component = 0

for i in nodes:
    if i not in visited: # DFS 도중 탐색한 곳이 아닌지
        if i in graph: # graph에 포함되어 있는지
            DFS(graph, i, visited)
            connected_component += 1

print(connected_component)

주석 X

n, m = map(int ,input().split())
visited = []
graph = {}

for i in range(m):
    f, s = map(int ,input().split())
    if not f in graph:
        graph[f] = []
    if not s in graph:
        graph[s] = []
    graph[f].append(s)
    graph[s].append(f)

def DFS(graph, start, visited):
    visited.append(start)
    print(start, end=' ')

    for neighbor in graph[start]:
        if neighbor not in visited:
            DFS(graph, neighbor, visited)

nodes = list(graph.keys())
connected_component = 0

for i in nodes:
    if i not in visited:
        if i in graph:
            DFS(graph, i, visited)
            connected_component += 1

print(connected_component)