Python depth first search using classes

[Aspect11]

So here's my current code:

class Vertex:
    def __init__(self, name):
        self.name = name
        self.connections = {}

    def addNeighbour(self, neighbour, cost):
        self.connections[neighbour] = cost

class Graph:
    def __init__(self):
        self.vertexs = {}

    def addVertex(self, newVertex):
        new = Vertex(newVertex)
        self.vertexs[newVertex] = new

    def addEdge(self, src, dest, cost):
        self.vertexs[src].addNeighbour(self.vertexs[dest], cost)

    def dfs(self, start, end, visited, path):
        visited[start] = True
        path.append(start)
        if start == end:
            # End node found
            print("found")
        else:
            # Use depth first search
            for connection in graph.vertexs[start].connections:
                if visited[connection.name] == False:
                    self.dfs(connection.name, end, visited, path)
        return path

def setup():
    graphList = {
        0: [1, 2],
        1: [3],
        2: [1],
        3: [0, 2]
    }
    count = 0
    graph = Graph()

    for i in range(4):
        graph.addVertex(i)

    for arr in graphList.values():
        for i in range(len(arr)):
            graph.addEdge(count, arr[i], 1)
        count += 1
    return graph

graph = setup()

traversalResult = graph.dfs(0, 3, [False, False, False, False], [])

print(traversalResult)

It can find the target node with depth first search, however, once the node has been found, it will continue to loop for one more time since it hasn't searched node 3 from node 0.

 

How can I fix this so it just stops once the node has been found?

 

Many thanks!

[Sauron]

You're not exiting the loop when you found something. If you're looping over 2 elements it's going to run the check on both elements even if one of them found something. This can be easily fixed by checking for return values: if the target has been found you should return the function and cause the parent function in the recursion to return as well.

    def dfs(self, start, end, visited):
        if start == end:
            # End node found
            print("found")
            return True
        else:
            # Use depth first search
            visited[start] = True
            for connection in graph.vertexs[start].connections:
                if visited[connection.name] == False:
                    if self.dfs(connection.name, end, visited):
                        return True
            return False

 

[BlueChinchillaEatingDorito]

40 minutes ago, Aspect11 said:

So here's my current code:

It can find the target node with depth first search, however, once the node has been found, it will continue to loop for one more time since it hasn't searched node 3 from node 0.

 

How can I fix this so it just stops once the node has been found?

 

Many thanks!

It looks like you're missing the stop condition for your recursive calls.

 

What I would do is add a return value to the dfs function that returns True when the node is found which I believe in your case is end. Every time you call dfs recursively, check if it returns True, if so, you can terminate immediately and skip any of the nodes that haven't been searched yet. And following the concept of recursion, that causes you to return True back up the chain so the program terminates.  

[Aspect11]

18 minutes ago, Sauron said:

You're not exiting the loop when you found something. If you're looping over 2 elements it's going to run the check on both elements even if one of them found something. This can be easily fixed by checking for return values: if the target has been found you should return the function and cause the parent function in the recursion to return as well.

    def dfs(self, start, end, visited):
        if start == end:
            # End node found
            print("found")
            return True
        else:
            # Use depth first search
            visited[start] = True
            for connection in graph.vertexs[start].connections:
                if visited[connection.name] == False:
                    if self.dfs(connection.name, end, visited):
                        return True
            return False

 

Thanks. I knew it was a simple solution, just didn't click with me. I'll try it out tomorrow.