탐색 알고리즘 DFS (2021/02/21)

DFS란 깊이 우선 탐색을 말한다.

 

탐색 시작 노드를 스택에 삽입하고 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

 

스택에 넣고 방문처리 스택에 넣고 방문처리 이 반복을 재귀함수를 이용하여 진행한다.

 

예제를 풀어보면,

 

graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]] 이렇게 나타낸 그래프가 있을 때 (통상적으로 1부터 시작하므로 0번을 비워놓는다.)

 

def dfs(graph,v,visited):
    visited[v]=True
    print(v,end=' ')
    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)

dfs 함수부터 살펴보면 graph와 v(탐색시작노드) visited(방문처리 여부)를 입력받는다.

 

visited[v]=True로 탐색시작노드를 방문처리하고 값을 출력한다.

 

입력받은 그래프를 차례로 탐색하면서 방문하지 않은 노드에 대해 다시 dfs함수를 이용해 처리한다.

 

 

아래 메인함수에서는 그래프의 값을 입력하고 visited를 전부 False처리해준다. 숫자는 총 8개이지만 그래프에서 0번째를 비워두었기 때문에 9를 입력한다. 그리고 dfs함수를 이용하여 1부터 탐색한다.

 

결과로는 

 

1 2 7 6 8 3 4 5

이 출력된다.

 

DFS에서는 스택과 재귀함수를 이용한다.