[Python] DFS 알고리즘

---

💡 DFS

• DFS(깊이우선탐색)는 그래프의 모든 정점을 방문하는 알고리즘
• 한 정점에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방식

💡 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다.

💡 파이썬 코드

# DFS 함수 구현
def dfs(graph, v, visited):

	visited[v] = True # 현재 노드를 방문 처리
    print(v, end = ' ') # 방문한 노드 출력
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph(v):
    	if i not visited[i]: # i가 방문 처리 되지 않았다면
        	dfs(graph, i, visited) # 재귀
            
# 그래프 정의
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * (len(graph) + 1) # 각 노드의 방문 여부를 나타내는 리스트 초기화

dfs(graph, 1, visited) # 1번 노드부터 DFS 탐색 시작

 

✔️ dfs 함수 : 현재 노드에서 시작하여 깊이 우선 탐색 수행

✔️ visited 리스트 : 각 노드의 방문 여부 나타내며, 초기에는 모든 노드가 방문하지 않은 상태로 초기화

✔️ 함수가 호출되면 현재 노드를 방문 처리하고 출력

✔️ 현재 노드와 연결된 다른 노드 중 방문하지 않은 노드가 있다면 해당 노드로 재귀 호출

✔️ 이 과정 반복