[Algorithm] DFS (깊이 우선 탐색) 알고리즘

DFS 알고리즘 (깊이 우선 탐색)

• 그래프의 모든 정점을 한 번만 방문하는 알고리즘

특징

• 재귀 함수로 구현
• 스택 자료구조를 이용
• FILO(First In Last Out): 먼저 들어온 데이터가 나중에 나간다.
• 시간복잡도 O(V+E)

 

• 한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 때 배열이 필요하며,
• 그래프는 인접 리스트로 표현한다.

알고리즘 정리

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

3. 스택 자료구조에 값이 없을 때까지 반복하기 

(이미 다녀간 노드는 방문배열을 바탕으로 재삽입하지 않는다.

 

 

 

수도코드 stack

Algorithm dfs(graph,v)
	stack.push(v)
    while (stack)
    	v = stack.pop() # 스택에서  노드를 꺼낸다
        traverse.append()
        if(!visited[v]) # 방문한 적이 없으면
        	visited[v] = true # 방문 배열 T 체크
            stack.push(unvisitied adjacent node) # 인접 노드를 스택에 삽입

 

• 참고자료

https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=148383 

학습 페이지

 

https://velog.io/@sangmin7648/%EA%B9%8A%EC%9D%B4%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89DFS%EA%B3%BC-%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89BFS