图的深度广度优先遍历 | JS

图的深度广度优先遍历 | JS

深度优先:先访问根结点,然后对根结点没访问过的相邻节点挨个进行深度优先遍历

广度优先:新建一个队列,根结点入队,队头出队并且访问,把队头没访问过的相邻节点入队,重复中间步骤直到队列为空。

 1 const graph = {
 2   0: [1, 2],
 3   1: [2],
 4   2: [0, 3],
 5   3: [3]
 6 }
 7 
 8 //深度优先遍历
 9 const visited = new Set();
10 const dfs = (n) => {
11   console.log(n);
12   visited.add(n);
13   graph[n].forEach(c => {
14     if(!visited.has(c)){
15       dfs(c);
16     }
17   })
18 }
19 dfs(2);
20 
21 //广度优先遍历
22 const visited = new Set();
23 visited.add(2);
24 const q = [2];
25 while(q.length) {
26   const n = q.shift();
27   console.log(n);
28   graph[n].forEach( c => {
29     if(!visited.has(c)){
30       q.push(c);
31       visited.add(c);
32     } 
33   })
34 }

 

图的深度广度优先遍历 | JS

上一篇:使用js来实现等腰三角形


下一篇:CSS总结