DFS는 형제 정점을 방문하기 전에 자식 정점을 방문합니다. 즉, 너비를 탐색하기 전에 특정 경로의 깊이를 탐색합니다. 스택(종종 재귀를 통한 프로그램의 호출 스택)은 알고리즘을 구현할 때 일반적으로 사용됩니다.
다음은 DFS가 작동하는 방식입니다 -
- 인접한 방문하지 않은 정점을 방문합니다. 방문한 것으로 표시하십시오. 그것을 표시하십시오. 스택에 푸시합니다.
- 인접한 정점이 발견되지 않으면 스택에서 정점을 팝업합니다. (인접한 정점이 없는 스택의 모든 정점을 표시합니다.)
- 스택이 비워질 때까지 규칙 1과 규칙 2를 반복합니다.
DFS 순회가 작동하는 방식에 대한 예시를 살펴보겠습니다.
| 단계 | 순회 | 설명 |
|---|---|---|
| 1 |  | 스택을 초기화합니다. |
| 2 |  | 마크 S 방문하여 스택에 넣습니다. S에서 방문하지 않은 인접 노드 탐색 . 우리는 세 개의 노드를 가지고 있으며 그 중 아무거나 선택할 수 있습니다. 이 예에서는 알파벳 순서로 노드를 사용합니다. |
| 3 |  | 마크 A 방문하여 스택에 넣습니다. A에서 방문하지 않은 인접 노드 탐색 . 둘 다 S 및 D A에 인접하지만 방문하지 않은 노드에만 관심이 있습니다. |
| 4 |  | D 방문 방문으로 표시하고 스택에 넣습니다. 여기에 B가 있습니다. 및 C D에 인접한 노드 둘 다 방문하지 않았습니다. 그러나 우리는 다시 알파벳 순서로 선택할 것입니다. |
| 5 |  | B를 선택합니다. 방문한 것으로 표시하고 스택에 넣습니다. 여기 B 방문하지 않은 인접 노드가 없습니다. 그래서 B를 팝니다. 스택에서. |
| 6 |  | 우리는 이전 노드로 돌아가기 위해 스택 상단을 확인하고 방문하지 않은 노드가 있는지 확인합니다. 여기에서 D를 찾습니다. 스택의 맨 위에 있어야 합니다. |
| 7 |  | 방문하지 않은 인접 노드만 D에서 왔습니다. C입니다. 지금. 그래서 우리는 C,를 방문합니다. 방문한 것으로 표시하고 스택에 넣습니다. |
C로 방문하지 않은 인접 노드가 없으므로 방문하지 않은 인접 노드가 있는 노드를 찾을 때까지 스택을 계속 팝업합니다. 이 경우에는 아무것도 없으며 스택이 비워질 때까지 계속 팝핑합니다. 이것을 JavaScript로 구현하는 방법을 살펴보겠습니다.
예시
DFS(node) {
// Create a Stack and add our initial node in it
let s = new Stack(this.nodes.length);
let explored = new Set();
s.push(node);
// Mark the first node as explored
explored.add(node);
// We'll continue till our Stack gets empty
while (!s.isEmpty()) {
let t = s.pop();
// Log every element that comes out of the Stack
console.log(t);
// 1. In the edges object, we search for nodes this node is directly connected to.
// 2. We filter out the nodes that have already been explored.
// 3. Then we mark each unexplored node as explored and push it to the Stack.
this.edges[t]
.filter(n => !explored.has(n))
.forEach(n => {
explored.add(n);
s.push(n);
});
}
} 글쎄, 그것은 쉬웠다. 우리는 정말로 스택을 위해 큐를 바꿨고 짜잔, 우리는 DFS를 가지고 있습니다. 2. DFS는 재귀를 사용하여 구현할 수도 있습니다. 그러나 더 큰 그래프는 호출 스택을 추적하기 위해 추가 메모리가 필요함을 의미하므로 이 경우에는 피하는 것이 가장 좋습니다.
−
를 사용하여 이것을 테스트할 수 있습니다.let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G");
g.DFS("A"); 출력
이것은 출력을 줄 것입니다.
A D E F B G C