DFS(Depth-First Search) : 깊이 우선 탐색

DFS: 깊이 우선 탐색

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조 혹은 재귀함수를 이용
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다.
     방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

이코테 강의 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번 노드가 연결 되어있는 정보
    [1,7], #2번 노드가 연결 되어있는 정보
    [1,4,5], #3번
    [3,5], #4번
    [3,4], #5번
    [7], #6번
    [2,6,8], #7번
    [1,7] #8번
]

#각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9

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

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

 

출처: 이코테 강의(DFS&BFS)