# 定义
- BFS(Breadth First Search), 广度优先搜索或者宽度优先搜索
- DFS(Depth First Search), 深度优先搜索
# DFS
一般使用递归实现
# BFS
一般使用队列实现
从A点出发，搜索结果是： A->B->C->D->E->F 从E点出发： E-> C->D->F->A->B
实现关键：queue
let graph = {
'A':['B','C'],
'B':['A','C','D'],
'C':['A','D','E'],
'D':['B','C','E'],
'E':['C','D','F'],
'F':['E']
}
function bfs(graph, startPoint) {
let queue = [];
let result = [];
queue.push(startPoint);
while(queue.length > 0) {
let point = queue.shift();
if(result.includes(point)) {
continue;
}
result.push(point);
let nodes = graph[point];
for(let point of nodes) {
queue.push(point);
}
}
return result;
}
bfs(graph, "A"); // ["A", "B", "C", "D", "E", "F"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 举个栗子: 获取目录下所有文件
# DFS
const path = require('path');
const fs = require('fs');
function dfsReadDir(dir, files = []) {
if(fs.statSync(dir).isFile()) {
files.push(dir);
return files;
}
fs.readdirSync(dir).forEach(item => {
const file = path.join(dir, item);
const stat = fs.statSync(file);
if(stat.isDirectory()) {
dfsReadDir(file, files);
}else {
files.push(file);
}
});
return files;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# BFS
const path = require('path');
const fs = require('fs');
function bfsReadDir(dir) {
const queue = [dir];
const results = [];
while(queue.length) {
const tempDir = queue.shift();
const stat = fs.statSync(tempDir);
if(!stat.isFile() && !stat.isDirectory()) {
continue
}
if(stat.isFile()) {
results.push(tempDir);
}else {
const files = fs.readdirSync(tempDir);
queue.push(...files.map(f => path.join(tempDir, f)));
}
}
return results;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20