[파이썬] 'DFS/BFS' 개념 및 예제

DFS - 깊이 우선 탐색 (스택 사용)

 

동작 과정)

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

 

예시)

def dfs(graph, v , visited):
	
    visited[v] = True # 현재 노드 방문 처리
    print(v, end =' ')
    
    for i in graph[v]: # 현재 노드와의 인접노드들 재귀적으로 dfs 처리
    	if not visited[v]:
        	dfs(graph, i , visited)
    
    


# 각 노드가 연결된 정보를 2차원 리스트로 표현
graph =[
		[],
        [2,3,8], # 1번노드
        [1,7],
        [1,4,5],
        [3,5],
        [3,4],
        [7],
        [2,6,8],
        [1,7]
        ]

# 각 노드 별 방문 여부 저장
visited = [False] * 9

dfs(graph, 1, visited)

 

동작 동영상)