DFS가 뭔가요? 그래프 자료를 깊이 우선 탐색하는 거란다

그래프 탐색 방법 중 하나인 DFS... 들어는 봤는데 

전에 자료구조 그래프 공부하면서 한 번 공부했었지만 한 번 해서 까먹었다ㅠ

다시 가보자고~!

 

 

그래프 용어
루트 노드: 최상위 정점(꼭짓점)
노드(node): 점
간선(edge): 점과 점을 연결하는 선
노드는 점이라고 이해하는 것이 편했다.

 

 

DFS(Deep First Search)

깊이 우선 탐색은 그래프(트리)의 자료구조 탐색 알고리즘이다. (DFS가 그래프 종류고 트리는 그래프 종류임)

 

 

DFS는 상위 노드에서 시작해서 하위 노드들을 모두 탐색하는 방식인데

탐색된 노드들을 스택이나 재귀 함수를 통해 관리한다.

 

그래서 스택이 선행되어야 한다...

2023.04.09 - [Computer Science/Database] - DFS를 이해하기 위한 선행으로 Stack과 Queue를 정리했다

 

 

그래프 탐색에서 핵심은 방문한 노드는 다시 방문하지 않는 것임

일반적으로 노드나 클래스에 visited 멤버 변수를 등록해 둔다 (다시 방문하지 않으려고) 

 

상위 노드와 연결된 노드(점)들은 한 번 방문하면 다시 방문하지 않는다.

아래 그림에서도 최상위노드인 1에서 상위노드인 2를 방문하고 -> 3 -> 4  하위노드를 모두 방문하고 다른 상위노드를 방문한다. 

 

DFS 탐색 과정 (https://developer-mac.tistory.com/64)

 

 

 

# DFS 함수 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
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)

 

 

 

DFS BFS 비교

DFS: 스택, 재귀함수로 구현, 최상위노드에서 상위노드와 연결된 하위노드들을 깊이 우선으로 방문하며 탐색

BFS: 큐로 구현, 최상위노드에서 가까운 점들부터 탐색 (너비우선탐색)

DFS(깊이우선탐색)과 BFS(너비우선탐색) (https://namu.wiki/w/BFS)