깊이 우선 탐색(DFS)
- 루트 정점 혹은 임의의 정점에서 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘
- 즉, 넓게 탐색하기 전에 깊게 탐색합니다.
- 스택 혹은 재귀함수를 통해 구현합니다.
- 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느립니다.
사용 예 )
- 모든 정점을 방문해야 할 때
- 가중치가 있는 간선을 이동할 때 혹은 여러 제약이 있을 경우
- 미로를 탐색 할 때 한 방향으로만 갈 수 있을때 까지 가보고 틀리다면 다시 가장 가까운 지름길을 찾을 때
방향성 그래프
code
// ----------------------- 방향 그래프 코드 -----------------------
function directedGraph() {
this.edges = {};
}
directedGraph.prototype.addVertex = function(vertex) {
this.edges[vertex] = {}
}
directedGraph.prototype.addEdge = function(goVertex, stopVertex, weight) {
if(weight == undefined) {
weight = 0
}
this.edges[goVertex][stopVertex] = weight;
}
directedGraph.prototype.removeEdge = function(goVertex, stopVertex) {
if(this.edges[goVertex] && this.edges[goVertex][stopVertex] != undefined) {
delete this.edges[goVertex][stopVertex];
}
}
directedGraph.prototype.removeVertex = function(vertex) {
for(var allEdge in this.edges[vertex]) {
this.removeEdge(allEdge, vertex);
}
delete this.edges[vertex]
}
// ----------------------- DFS 탐색 코드 -----------------------
directedGraph.prototype.traverDFS = function(vertex) {
var visited = {}
this._traverDFS(vertex, visited);
}
directedGraph.prototype._traverDFS = function(vertex, visited) {
visited[vertex] = true;
console.log(vertex, '방문 완료')
for(var nextVertex in this.edges[vertex]) {
if(!visited[nextVertex]) {
this._traverDFS(nextVertex, visited);
}
}
}
// ----------------------- 방향 그래프 정점,간선 추가 -----------------------
var graph2 = new directedGraph();
graph2.addVertex('A')
graph2.addVertex('B')
graph2.addVertex('C')
graph2.addVertex('D')
graph2.addVertex('E')
graph2.addEdge('A', 'B', 1)
graph2.addEdge('B', 'C', 1)
graph2.addEdge('B', 'D', 2)
graph2.addEdge('D', 'E', 5)
console.log(graph2.edges)
// A
// B
// C D
// E
// ----------------------- DFS A 탐색 -----------------------
graph2.traverDFS('A')
// A 방문 완료
// B 방문 완료
// C 방문 완료
// D 방문 완료
// E 방문 완료
// ----------------------- DFS B 탐색 -----------------------
graph2.traverDFS('B')
// B 방문 완료
// C 방문 완료
// D 방문 완료
// E 방문 완료
// ----------------------- DFS C 탐색 -----------------------
graph2.traverDFS('C')
// C 방문 완료
// ----------------------- DFS D 탐색 -----------------------
graph2.traverDFS('D')
// D 방문 완료
// E 방문 완료
// ----------------------- DFS E 탐색 -----------------------
graph2.traverDFS('E')
// E 방문 완료
설명
// ----------------------- DFS 탐색 코드 -----------------------
// (1) - 방문중인 정점
// (2) - 모든 정점 방문 했는지 안했는지 여부
// true => 방문 완료, undefined => 방문 미완료
// (3) - 방문중인 정점에 인접정점
// 설명
// 방문중인 정점에 방문했다고 visited객체에 true로 저장한다
// 방문중인 정점에 인접정점을 찾고 해당 인접정점이 방문이 미완료일 경우
// 재귀함수를 이용하여 인접정점을 방문한다.
// 재귀함수를 통해 호출되기때문에 다음 분기를 넘어가기 전에 해당 분기를 가장 깊게 탐색한다
// 데이터 상황
// {
// A: { B: 1, Q: 5 },
// Q: { P: 5, R: 5 },
// P: {},
// R: {},
// B: { C: 1, D: 2 },
// C: { CC: 1 },
// CC: { ccc: 1, CCC: 1 },
// CCC: {},
// ccc: {},
// D: { E: 5 },
// E: {}
// }
// 현재 데이터 상황 그림으로 표현
// A
// B Q
// C D P R
// CC E
// ccc CCC
directedGraph.prototype.traverDFS = function(vertex) {
var visited = {}
this._traverDFS(vertex, visited);
}
directedGraph.prototype._traverDFS = function(vertex, visited) {
visited[vertex] = true; // 방문 중인 정점 체크(true)로 하기
console.log(vertex, '방문 완료') // (1)
for(var checkVisited in this.edges) {
console.log(checkVisited, '의 방문 상태 =>', visited[checkVisited]) // (2)
}
for(var nextVertex in this.edges[vertex]) {
console.log('인접 정점 : ', this.edges[vertex]) // (3)
console.log("")
if(!visited[nextVertex]) {
this._traverDFS(nextVertex, visited);
}
}
}
// ----------------------- 방향 그래프 정점,간선 추가 -----------------------
var graph2 = new directedGraph();
graph2.addVertex('A')
graph2.addVertex('Q')
graph2.addVertex('P')
graph2.addVertex('R')
graph2.addVertex('B')
graph2.addVertex('C')
graph2.addVertex('CC')
graph2.addVertex('CCC')
graph2.addVertex('ccc')
graph2.addVertex('D')
graph2.addVertex('E')
graph2.addEdge('A', 'B', 1)
graph2.addEdge('B', 'C', 1)
graph2.addEdge('C', 'CC', 1)
graph2.addEdge('CC', 'ccc', 1)
graph2.addEdge('CC', 'CCC', 1)
graph2.addEdge('B', 'D', 2)
graph2.addEdge('D', 'E', 5)
graph2.addEdge('A', 'Q', 5)
graph2.addEdge('Q', 'P', 5)
graph2.addEdge('Q', 'R', 5)
console.log(graph2.edges)
// ----------------------- DFS A 탐색 -----------------------
graph2.traverDFS('A')
// A 방문 완료
// B 방문 완료
// C 방문 완료
// CC 방문 완료
// ccc 방문 완료
// CCC 방문 완료
// D 방문 완료
// E 방문 완료
// Q 방문 완료
// P 방문 완료
// R 방문 완료
// ----------------------- DFS B 탐색 -----------------------
// graph2.traverDFS('B')
// B 방문 완료
// C 방문 완료
// CC 방문 완료
// ccc 방문 완료
// CCC 방문 완료
// D 방문 완료
// E 방문 완료
// ----------------------- DFS Q 탐색 -----------------------
// graph2.traverDFS('Q')
// Q 방문 완료
// P 방문 완료
// R 방문 완료
// ----------------------- DFS C 탐색 -----------------------
// graph2.traverDFS('C')
// C 방문 완료
// CC 방문 완료
// ccc 방문 완료
// CCC 방문 완료
// ----------------------- DFS D 탐색 -----------------------
// graph2.traverDFS('D')
// D 방문 완료
// E 방문 완료