사실 엄청간단한 개념인데 모르는 사람들이 좀 있는 것 같아서,

간단히 적어본다.


구술면접에서 그냥 개념정도 설명할 수 있는 정도니까, 토막글 처럼 봐바.

대부분 알고있지만, 늅들을 위해 딴지좀 걸지말아줘. 너희도 몰랐던 시절이 있었잖아?


BFS 와 DFS


이진트리를 순회하는 방법[정순회,좌순회,우순회] 와는 다르게

BFS 와 DFS는 그래프 순회의 방법들의 이름이야. 

그래프가 뭐냐면, 대충 요런 형태를 취하는 자료구조야.

트리와는 다르게 여러 노드들이 서로 연결되어 있지?

(사실 그래프 안에 트리라는 개념이 포함되어 있어.)




DFS와 BFS는 순회하는 노드의 순서(방식)에 차이가 있어.

하지만 그래프탐색에서 유의할점은 DFS 든 BFS 든 꼭 방문한 노드는 방문했다고 기록해두자!

일반적으로 노드 구조체나 클래스에 visted 멤버변수를 등록해서 체크해두는게 일반적이야.


DFS (Depth   First Search) : 깊이 우선 탐색

BFS (Breadth First Search) : 넓이 우선 탐색


DFS는 한국말로 깊이 우선 탐색이야.

대충 저 그래프를 순회한다고 할때, 처음 시작하는 노드를 "A"로 잡아보자.

A와 연결된 노드들에는 B , C , D 가 있지?

DFS 는 A를 방문한뒤, 연결되어있는 노드중 하나를 탐색해. 이런구조가 재귀 되는거지.

즉 A를탐색한뒤 A와 연결된 B를 탐색한뒤, 다시 A와 연결된 노드를 탐색하지 않고, B와 연결된 노드들을 탐색하는 것 DFS 이야!


[가상코드]

void search(Node n){
if(n==null) return;   

visit(n);

n.visited=true;

for ( i<n.connect ){ // 노드 n과 연결된 노드들 만큼 for 문을 돌려.
   if(n.connect[i].visted==false){

      search(n.connect[i]);

   }

}

}




다음은 BFS인데,

BFS의 핵심키워드는 바로, "큐"야!

큐 알지? 자료구조중하나로, First In First Out [FIFO] 형식을 띄는 자료구조인데.

DFS에서 유추해볼수 있듯이 BFS의 의미는

A를탐색한뒤 A와 연결된 B를 탐색한뒤, 다시 A로 돌아와 B를 제외한 다른 A와 연결된 노드를 탐색하는것이 BFS 이야!


이때, 사용되는 자료구조가 "큐" 인데.

이건 가상코드 쓰기가 귀찮네 ㅎㅎ

http://programbasic.tistory.com/521

요거봐 ㅋㅋ