In a depth first search for a path, a "not iterable" error is thrown-CodePudding

I am new to algorithms and data structures, and I have tried making a depth search for a graph but depending on the parameters it sometimes throws

TypeError: graph[start] is not iterable

In the below code, the algorithm is executed twice on the same graph, but with a different end-node: the first call returns the expected result, but the second one triggers the error:

const graph = {}
graph.a = ['b', 'c']
graph.b = ['f']
graph.c = ['d', 'e']
graph.d = ['f']
graph.e = ['f']
graph.f = ['g']

function depthSearch(graph, start, end) {
    if(start === end) return true
    if(start.visited) return false

    start.visited = true

    for(let neighbor of graph[start]) {
        if(!neighbor.visited) {
            let reached = depthSearch(graph, neighbor, end)
            if(reached) return true
        }
    }
    return false
}

console.log(depthSearch(graph, 'a', 'g')) //this works and returns true
console.log(depthSearch(graph, 'a', 'd')) //this causes TypeError: graph[start] is not iterable

CodePudding user response：

This happens because you have not defined graph.g, while "g" is a vertex that is mentioned as neighbor of "f".

If you don't want to add leaf nodes explicitly at the start, you can provide a fall-back value:

 graph[start] ?? []

However, there is another problem in your code:

 start.visited

...because start is a string primitive, so it does not have that property, nor can it get it. I would suggest introducing a Set for the purpose of tracking visited nodes. Pass it as argument, and give it a default value so that each top-level call of depthSearch starts off with an empty set.

Not an issue, but it is overkill to have two places where you check whether a node has been visited. Just make the recursive call without this check and trust the recursive call to detect that itself.

const graph = {};
graph.a = ['b', 'c'];
graph.b = ['f'];
graph.c = ['d', 'e'];
graph.d = ['f'];
graph.e = ['f'];
graph.f = ['g'];

function depthSearch(graph, start, end, visited=new Set) {
    if(start === end) return true;
    if(visited.has(start)) return false;
    visited.add(start);

    for(let neighbor of graph[start] ?? []) {
        let reached = depthSearch(graph, neighbor, end, visited);
        if(reached) return true;
    }
    return false;
}

console.log(depthSearch(graph, 'a', 'g')); // true
console.log(depthSearch(graph, 'a', 'd')); // true