recursiongraph-algorithmdepth-first-searchminimum-spanning-treekruskals-algorithm

Return the path between two nodes in a minimum spanning tree


I have a minimum spanning tree created using Kruskal's algorithmstored in a map of key:string and data:set(string)

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

I am trying to write an algorithm that will return the path between a specified start and end node

$ findPath A F
> A B D E F

$ findPath F C
> F E D B C

I think I should use some kind of modified depth first search but I am not sure how to implement the algorithm or how to store the nodes that form the path. I don't believe I have to worry about marking nodes as "visited" since there are no cycles in a MST.

There are some similar questions but I haven't been able to find any that can be applied to my specific scenario, they seem to only deal with a non-MST and only return if a path can be found between two nodes, which in my case I already know that there is a path between every node and I also require a list of nodes on the path.

EDIT The answer converted to c++, probably not the cleanest code but it works

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;
}

Solution

  • 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', []))