🌼 DFS(Depth-First-Search) Algorithm

🌼 DFS(Depth-First-Search) Algorithm

• DFS는 깊이 우선 탐색이라고도 부르며, 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
• DFS는 Stack 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.
  1. 탐색 시작노드를 스택에 넣고, 방문처리한다.
  2. 스택의 최상단 노드와 인접한 노드 중 방문하지 않은 노드가 있다면, 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없다면 스택 최상단 노드를 pop한다.
  3. 2번의 과정을 수행할 수 없을때까지(stack이 empty할때까지) 반복한다.

 

🌼 재귀함수로 DFS 구현

# 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)

# 실행 결과
# 1 2 7 6 8 3 4 5

 

🌼 재귀함수로 DFS 구현

# DFS 메서드 정의
def dfs(graph, v):
    visited = [False] * len(graph)
    stack = []
    stack.append(v)

    while stack:
        v = stack.pop()

        if not visited[v]:
            print(v, end=' ')
            visited[v] = True

        for w in sorted(graph[v], reverse=True):
            if not visited[w]:
                stack.append(w)

# 각 노드가 연결된 정보를 표현(2차원 배열)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 정의된 DFS 함수 호출
dfs(graph, 1)

# 실행 결과
# 1 2 7 6 8 3 4 5