깊이 우선 탐색 (DFS) / 너비 우선 탐색 (BFS)

카테고리 없음

JUNGKEUNG 2024. 7. 27. 15:14

깊이 우선 탐색 (DFS) 와 너비 우선 탐색(BFS) 는 언제 사용하는지 알아보았다. DFS 와 BFS는 그래프 검색할때 자주 사용한다.

그렇다면 그래프는 무엇일까?

그래프는 노드와 그 노드를 연결하는 간성르 하나로 모아 놓은 것이다. 방향성이 있을수도 있고 없을수도 있다.

방향성이 없는 그래프를 무방향 그래프라 한다.

무방향 그래프에서 간선에 방향 정포가 포함된 그래프를 방향 그래프라 한다

각각의 장점에서 다른 모든 장점을 연결한 그래프를 완전 그래프라 한다

1. 인접행렬

- 2차원 배열에 표현하는 방법

- 그래프를 표에다 표현하는 방법

- 서로 연결된 노드들은 1로 표현하고 연결이 업으면 0으로 2차원 배열방을 채우는 방법

1. 인접리스트

- 배열에 노드들을 나열하고 관계를 연결 리스트로 표현하는 방법

- 배열 방에 모든 노드들을 집어넣고 각 배열방에 있는 해당 노드와 인접한 노드들을 연결리스트로 나열해서 저장하는 방법

그럼 위 그림에서 노드의 개수는 몇개일까?

-> 노드들은 관계를 나타낸다. 가넛ㄴ의 개수를 m 이라 할 떄, 총 노드의 개수는 2m 개 생긴다.

연결은 두개의 노드가 서로 연결되니 원래 간선 개수보다 2배 많아지는것이 이유이다.

깊이 우선 탐색 (DFS, Depth-First Search)
- inorder, preorder, postorder 순회 방법이 DFS 에 속한다.
- 하나의 자식노드를 방문했으면 그 자식들을 끝까지 파고든다.
- 자식노드의 마지막 노드를 만날때까지 반복한 후 형제노드를 방문한다.

너비 우선 탐색(BFS, Breadth-First Search)
- 시작점에서 자식노드를 모두 방문하고 , 자식의 자식을 방문하는 식으로 검색한다.
- 즉, 레벨단위로 검색이 이루어진다.
- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 유용하다.
- DFS 를 이용하게되면 정답에서 동떨어진 경로를 계속해서 탐색해 나갈 수 있다.

참고 자료