파이선 DFS 설명 및 구현

※ DFS란?

 

DFS.

 

Depth First Search

 

말그대로 깊이 우선 탐색

 

그래프에서 가장 깊은 부분을 먼저 탐색한다

 

 

※ DFS구현?

- DFS는 스택 or 재귀를 통해서 구현한다

=> 스택을 재귀로도 구현하니까 당연한말이다.

 

※ DFS 과정은?

 

1. 탐색을 시작할 노드를 스택에 삽입하고 방문 처리한다

2. 스택의 최상단 노드에 인접한 노드 중에 방문하지 않은 노드가 있으면 방문 처리하고 스택에 집어 넣는다

- 최상단 노드에 인접한 노드 중 방문하지 않는 노드가 없다면 스택에서 꺼낸다.

3. 더이상 2번을 수행할 수 없을 때까지 반복한다.

 

※ DFS 구현

def dfs(graph, v, visited):
	visited[v] = True
    print(v, ends=' ')
    
    for i in graph[v]:
    	if not visited[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]*9

dfs(graph,1,visited)