[알고리즘] 그래프 탐색 방법 _BFS 와 DFS 쉽게 이해하기.

안녕하세요. 우당탕탕 개발일지 입니다. BFS,DFS 저도 용어는 많이 들어보고 공부할까 망설이다. 이제야 책을 폈습니다.ㅎㅎ BFS와 DFS를 이해하기 위해서 필요한 내용들을 제 블로그에 따로 정리해 뒀으니 참고 해주시면 감사하겠습니다!  저는 " 트리 -> 이진 탐색 트리 -> 그래프"를 공부하고 나니 이해가 잘되었던 것 같습니다.  급하게 공부 하셔야 하시는 분 이 순서대로 공부하시면 될 것 같습니다.  코드트리 Lv3에 그래프 부분이 설명이 무척 잘 되어 있습니다. 

 

 

2025.04.08 - [[알고리즘]] - [알고리즘] graph 기초 + 용어 정리(트리 기초)

 

 

 

※DFS와 BFS는 성능상의 차이는 없음. 

1. DFS (Depth First Search)

: 깊이 우선 탐색 = 가장 깊은 곳을 먼저 다 탐색 해본 후 이전과정으로 돌아감.  

 

★ 재귀로 많이 구현 함 => 즉, 스택을 사용. →LIFO

 

시간복잡도:  O(노드수 +간선수)  = O(V+E)

 

function dfs (pos)
{
	visit(pos)
    for child  of pos
    	if visited [child]==false
        	dfs(child)

}

 

 

DFS 예제 ) 

 

5 - 2 -  1  - 3 - 6 - 7

             l

            4

 

Q) root node가 1일 때,  DFS로 탐색하는 순서를 쓰시오. (우선 순위가 같을 때는 작은 숫자를  우선함. )

 

A )  1, 2, 5, 3 ,6 ,7 ,4

 

---

2.BFS (Breadth Frist Search)

: 너비 우선 탐색  -> 길이가 같은 노드를 전부 탐색하고 이전과정으로 돌아감.

 

★큐(Queue)로 구현 ->FIFO 

 

시간복잡도:  O(노드수 +간선수)  = O(V+E)

 

function bfs(pos)
{
	set Q =Queue
    Q.push(pos)
    visit(pos)
    
    while Q is not empty
    	set node = Q.pop()
        for child of node
        	if visited[child] ==false
            	visit(child)
                Q.push(child)


}

 

 

BFS 예제 ) 

 

5 - 2 -  1  - 3 - 6 - 7

             l

            4

 

Q) root node가 1일 때,  BFS로 탐색하는 순서를 쓰시오. (우선 순위가 같을 때는 작은 숫자를  우선함. )

 

A) 1 , 2, 3, 4, 5, 6, 7