javascript - 图的深度优先遍历 - javascript

Question

我正在努力学习图形，并在 javascript 中实现了以下深度优先搜索。 DFS 功能工作正常，但 checkRoutes 功能是我麻烦的根源。 checkRoutes 函数接受两个输入，如果两个节点/顶点之间存在可能的路径则返回 true，否则返回 false。它通过从一个节点开始，检查邻接列表，然后通过递归检查邻接列表中每个项目的邻接列表来实现这一点。

我的解决方案仅适用于一种情况 - 当您检查两个顶点一次时，但由于我在全局存储 possibleVertices 数组的方式，“possibleVertices”不会每次都被清除。我如何推送和存储到“checkRoute”内的“possibleToVisit”数组而不是在此类中全局存储？将此数组存储在构造函数中会更好吗？

var possibleToVisit = [];

function dfs(v) {
  this.marked[v] = true;
  if (this.adj[v] !== undefined) {
    console.log("visited vertex " + v);
  }

  for (var i = 0; i < this.adj[v].length; i++) {
    var w = this.adj[v][i];
    if (!this.marked[w]) {
      possibleToVisit.push(w)
      this.dfs(w);
    }
  }
  console.log(possibleToVisit);
}

function checkRoute(v, v2) {
  this.dfs(v);
  if (possibleToVisit.indexOf(v2) === -1) {
    return false;
  }
  return true;
}
g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
// g.showGraph();
// g.dfs(0);
console.log(g.checkRoute(0, 4));//true
console.log(g.checkRoute(0, 5));//false

https://jsfiddle.net/youngfreezy/t1ora6ab/3/#update

Answer 1

您可以编写一个 DFS“启动器”函数，它将重置所有变量，并在必要时返回一些内容:

function Graph(v) {
    this.startDfs = startDfs;
    this.possibleToVisit = [];
}

// ...

function startDfs(v) {
    this.possibleToVisit = []; // here, you can reset any values

    this.dfs(v);

    return true; // here, you can return a custom object containing 'possibleToVisit'
}

并且仅使用 startDfs 调用它:

function checkRoute(v, v2) {
    this.startDfs(v);
    if (this.possibleToVisit.indexOf(v2) === -1) {
        return false;
    }
    return true;
}

这是更新的 JSFiddle .