# 动画：如何用广度和深度优先搜索找到女朋友？

IT综合 作者：zone7 时间：2020-04-09 14:55:07 0 删除 编辑

`` 1constructor(v) { 2   this.v = v; 3   this.adj = []; 4   this.visited = []; 5   this.pre = []; 6   this.queue = []; 7   this.found = false; 8   for (let i = 0; i < v; i++) { 9     this.adj[i] = new Array();10   }11}1213// 无向图的边存储两次14addEdge(s, t) {15  this.adj[s].push(t)16  this.adj[t].push(s)17}``

`` 1class Graph { 2        constructor(v){ 3          this.v = v; 4          this.adj = []; 5          this.visited = []; 6          this.pre = []; 7          this.queue = []; 8          for(let i = 0;i < v;i++) { 9            this.adj[i] = new Array();10          }11        }1213        // 无向图的边存储两次14        addEdge(s, t) {15          this.adj[s].push(t)16          this.adj[t].push(s)17        }1819        // 递归打印数组20        // 0 ——> 621        print(preArr, s, t) {22          if(preArr[t] !== -1 && s !== t){23            this.print(preArr, s, preArr[t])24          }25          console.log(t);26        }2728        // 广度优先遍历最短路径29        // s 起始  t 终点30        bfs1(s, t) {31          var queue = this.queue,32              pre = this.pre,33              visited = this.visited,34              adjTemp = this.adj;3536          // 判断起始点是否相同37          if(s === t) return 0;38          queue.push(s);39          visited[s] = true;4041          // 初始化搜索路径42          for(let i = 0;i < this.v;i++){43            pre[i] = -1;44            visited[i] = false;45          }4647          // 开始遍历队列48          while(queue.length !== 0) {49            console.log(queue)50            // 出队51            const temp = queue.shift();5253            // 遍历所有于 temp 相邻的结点54            for(let i = 0; i < adjTemp[temp].length;i++){5556              // console.log(adjTemp)57              var q = adjTemp[temp][i];5859              // 如果没有遍历过60              if(!visited[q]){61                // 并记录搜索路径62                pre[q] = temp6364                // 判断是否为终点65                if(q === t){66                  // 打印路径67                  this.print(pre,s,t)68                  // console.log(pre)69                  return;70                }7172                // 存到队列汇总，等待下一次的遍历73                queue.push(q)7475                // 记录已访问的结点76                visited[q] = true77              }78            }79          }80        }81      }``

`` 1class Graph { 2      constructor(v) { 3        this.v = v; 4        this.adj = []; 5        this.visited = []; 6        this.pre = []; 7        this.queue = []; 8        this.found = false; 9        for (let i = 0; i < v; i++) {10          this.adj[i] = new Array();11        }12      }1314      // 无向图的边存储两次15      addEdge(s, t) {16        this.adj[s].push(t)17        this.adj[t].push(s)18      }1920      // 递归打印数组21      // 0 ——> 622      print(preArr, s, t) {23        if (preArr[t] !== -1 && s !== t) {24          this.print(preArr, s, preArr[t])25        }26        console.log(t);27      }2829      // 深度优先遍历最短路径30      // s 起始  t 终点31      dfs1(s, t) {32        const v = this.v,33          pre = this.pre,34          queue = this.queue,35          visited = this.visited;3637        // 初始化 pre38        for (let i = 0; i < v; i++) {39          pre[i] = -1;40        }4142        this.recurDfs(s, t, pre, visited);43        this.print(pre, s, t);44      }4546      recurDfs(s, t, pre, visited) {47        if (this.found) return;4849        // 判断是否为终点50        if (s == t) {51          this.found = true;52          return;53        }5455        // 记录第一个已访问结点56        visited[s] = true;5758        for (let i = 0; i < this.adj[s].length; i++) {59          let temp = this.adj[s][i];6061          // 判断是否已经访问过62          if (!visited[temp]) {6364            // 记录未访问结点的路径65            pre[temp] = s;6667            // 回溯遍历68            this.recurDfs(temp, t, pre, visited)69          }70        }71      }72    }``

• 博文量
19
• 访问量
19253