在最小生成树中返回两个节点之间的路径。

Question

我使用Kruskal算法创建了一棵最小生成树，并将其存储在一个键为字符串类型、数据为字符串集合类型的映射中。

mst = { "A" : ["B"]
        "B" : ["A", "C", "D"]
        "C" : ["B"]
        "D" : ["B", "E"]
        "E" : ["D", "F"] }

我正在尝试编写一个算法，以返回指定起点和终点节点之间的路径。

$ findPath A F
> A B D E F

$ findPath F C
> F E D B C

我认为我应该使用某种修改过的深度优先搜索算法，但我不确定如何实现该算法或如何存储形成路径的节点。我认为我不必担心将节点标记为“已访问”，因为MST中没有循环。

有一些类似的问题，但我还没有找到可以应用于我的特定情况的问题，它们似乎只处理非MST，并且仅返回两个节点之间是否可以找到路径，在我的情况下，我已经知道每个节点之间都有路径，并且我还需要路径上的节点列表。

编辑： 答案转换为C ++，可能不是最干净的代码，但它可以工作。

vector<string> findPath(map<string, set<string>> mst, string src, string dest, vector<string> path) {
    if(src == dest) {
        return path;
    }
    set<string> possible = mst[src];
    for(vector<string>::iterator it = path.begin(); it != path.end(); it++) {
        if(possible.find(*it) != possible.end())
            possible.erase(*it);
    }
    for(set<string>::iterator it = possible.begin(); it != possible.end(); it++) {
        vector<string> a = path;
        if(find(a.begin(), a.end(), src) == a.end())
                a.push_back(src);
        vector<string> p = findPath(mst, *it, dest, a);
        if(p[0] != "FALSEBEGINNING") {
            return p;
        }
    }
    vector<string> p = path;
    p[0] = "FALSEBEGINNING";
    return p;
}

- Sean

Answer 1

const mst = {
  A: ['B'],
  B: ['A', 'C', 'D'],
  C: ['B'],
  D: ['B', 'E'],
  E: ['D', 'F']
}

const findPathTraversal = (mst, src, dest, path) => {
  const findPath = (mst, src, dest, path) => {
    if (src === dest) return path
    let possible = mst[src]
    possible = possible.filter(v => !path.includes(v))
    for (let i = 0; i < possible.length; i++) {
      let a = path
      if (!a.includes(src)) a.push(src)
      let p = findPath(mst, possible[i], dest, a)
      if (p != -1) return path
    }
    return -1
  }
  let ans = findPath(mst, src, dest, path)
  ans.push(dest)
  return ans
}

console.log(findPathTraversal(mst, 'A', 'F', []))

- Naor Tedgi

---

这个算法完美运行！我正在尝试在c++中实现它，但我遇到了一些问题，每次它都返回一个空路径，即使我可以看到它正在访问正确的路径。 - Sean