깊이 우선 탐색 DFS와 너비 우선 탐색 BFS
하나의 정점에서 시작하여 그래프에 있는 모든 정점(node)을 한 번씩 방문하는 것을 그래프 탐색이라고 한다. 그래프 탐색 방법으로 깊이 우선 탐색과 너비 우선 탐색이 있다.
위의 그래프를 각각 DFS와 BFS로 탐색했을 때 :
DFS: A -> B -> D -> E -> F -> C -> G -> H -> I -> J
BFS: A -> B -> C -> D -> G -> H -> I -> E -> F -> J
깊이 우선 탐색 DFS(Depth-First Search)
시작 노드에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선(edge)이 있는 노드로 되돌아와서 다른 방향의 간선으로 탐색을 계속하여 모든 노드를 방문하는 탐색 방법이다. 구현 방법으로는 스택을 이용한 방법과 재귀를 이용한 방법이 있다.
스택을 이용한 DFS
function DFSMain() {
const visited = [];
const graph = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'G', 'H', 'I'],
D: ['B', 'E', 'F'],
E: ['D'],
F: ['D'],
G: ['C'],
H: ['C'],
I: ['C','J'],
J: ['I']
}
const DFS = ((node) => {
const stack = [node];
visited.push(node);
console.log(node);
while (stack.length > 0) {
const currentNode = stack[stack.length-1];
let flag = true;
for (const nodeToVisit of graph[currentNode]) {
if (!visited.includes(nodeToVisit)) {
console.log(nodeToVisit)
stack.push(nodeToVisit);
visited.push(nodeToVisit);
flag = false;
break;
}
}
if (flag) {
stack.pop();
}
}
});
DFS('A')
}
DFSMain();
시작 노드를 스택에 넣어 주고 시작한다.
스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 이 과정을 스택이 빈 상태가 될 때까지 반복한다.
stack:
A -> A, B -> A, B, D, -> A, B, D, E -> A, B, D -> A, B, D, F -> A, B, D, -> A, B -> A -> A, C -> A, C, G -> A, C -> A, C, H -> A, C -> A, C, I -> A, C, I, J -> A, C, I -> A, C -> A -> []
재귀를 이용한 DFS
function DFSMain() {
const visited = [];
const graph = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'G', 'H', 'I'],
D: ['B', 'E', 'F'],
E: ['D'],
F: ['D'],
G: ['C'],
H: ['C'],
I: ['C','J'],
J: ['I']
}
const DFS = ((node) => {
console.log(node);
if (graph[node].length > 0) {
for (const nodeToVisit of graph[node]) {
if (!visited.includes(nodeToVisit)) {
visited.push(nodeToVisit);
DFS(nodeToVisit);
}
}
}
});
visited.push('A');
DFS('A')
}
DFSMain();
현재 노드에서 방문할 노드가 있다면 재귀 호출하여 한층 깊이 들어간다.
너비 우선 탐색 BFS(Breadth-First Search)
너비 우선 탐색은 시작 노드로부터 인접한 노드들을 모두 차례로 방문한 후 방문했던 노드를 다시 시작점으로 하여 인접한 노드들을 차례로 방문하는 방법으로,
가까운 노드들을 먼저 방문하고 멀리 있는 노드들은 나중에 방문하는 탐색 방법이다.
구현 방법으로는 큐를 이용한 방법이 있다.
function BFSMain() {
const graph = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'G', 'H', 'I'],
D: ['B', 'E', 'F'],
E: ['D'],
F: ['D'],
G: ['C'],
H: ['C'],
I: ['C','J'],
J: ['I']
}
const BFS = ((startNode) => {
const que = [startNode];
const visited = [];
while (que.length > 0) {
const node = que.shift();
visited.push(node);
console.log(node)
for (const nodeToVisit of graph[node]) {
if (!visited.includes(nodeToVisit)) {
visited.push(nodeToVisit);
que.push(nodeToVisit);
}
}
}
});
BFS('A');
}
BFSMain();
큐에 값이 존재하는 동안 현재 노드에서 방문할 수 있는 노드들을 모두 큐에 넣고 큐에 왼쪽부터(index: 0) shift()를 통해 꺼내와 다시 방문할 수 있는 노드를 탐색한다.