Is there a way to avoid revisiting/keep track of visited nodes in recursive traversal without class attribute or passed parameter?

Question

Is there a way to do a graph based depth first traversal recursively without passing a "visited" parameter set of visited nodes (or having one as a class attribute or global variable)?

The pseudo code on wikipedia seems to indicate it is necessary.

My code (below) works after I added the default parameter to the signature given me. I didn't want to mess with the function signature at all because it's being called inside a unit test. However, a default parameter proved to be both useful and harmles, but is this the only way I could have done it, assuming I had to use recursion?

    def dft_recursive(self, starting_vertex, visited = set()):
        """
        Print each vertex in depth-first order
        beginning from starting_vertex.

        This should be done using recursion.
        """
        print(starting_vertex)
        visited.add(starting_vertex)
        for neighbor in self.vertices[starting_vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                self.dft_recursive(neighbor, visited)

Answer 1

In order to demonstrate this let's consider the following undirected graphs Graph:

1. Using Node Class instance

Implementing a Node's Class which which stores the Visited boolean Flag status itself. Also note as se store the neighbours within the Node's Class itself.

class Node:

    def __init__(self, name):
        self.name = name
        self.neighbours = []
        self.visited = False
        self.previous_node = None # NOTE: This is just to show the printed result not really needed

    def __str__(self):
        return f'{self.name} can go to = {self.neighbours}, is Visited? = {self.visited}'

    def __repr__(self):
        return f'{self.name}'

    def add_path(self, node_to):
        if isinstance(node_to, Node):
            if node_to not in self.neighbours:
                self.neighbours.append(node_to)
            else:
                print(f'Error, added node_to is already a neighbour of {self.name}')
        else:
            print(f'Error adding the new Node neighbour, it must be a instance of Node')

    def has_unvisited_neighbour(self):  
        """Check the Node's neighbours, return False if even one node is False hence not visited"""
        check_neighbours = [node.visited for node in self.neighbours]
        return all(check_neighbours)


class Graph:

    def __init__(self, nodes: list):
        self.nodes = {node: Node(node) for node in nodes}

    def create_graph(self, paths: list):
        node_from, nodes_to = paths
        if node_from in self.nodes:
            get_node_from = self.nodes.get(node_from)
            for node in nodes_to:
                get_node_to = self.nodes.get(node)
                self.nodes[node_from].add_path(get_node_to)
                self.nodes[node].add_path(get_node_from)
        else:
           print('Error while creating Graph, an unknown node was entered :(')

    def __repr__(self):
        return f'Graph({self.nodes})'

    def show_nodes(self):
        for node in self.nodes.values():
            print(node)

    def dft_recursive(self, starting_vertex):    
        starting_vertex = self.nodes[starting_vertex]
        starting_vertex.visited = True
        for neighbor in starting_vertex.neighbours:
            if not neighbor.visited:
                neighbor.visited = True
                neighbor.previous_node = starting_vertex # NOTE: This is just to show the printed result not really needed
                if not neighbor.has_unvisited_neighbour():  # If False means we reached a dead end
                    print(starting_vertex.name, end=' --> ')
                    self.dft_recursive(neighbor.name)
                else: 
                    print(neighbor.previous_node.name, '--> ', neighbor.name, '| ')
                    continue

nodes_list = ['Earth', 'Moon', 'Mars', 'Venus',
              'Mercury', 'Jupiter', 'Saturn',
              'Neptune', 'Uranus', 'Sun', 'Comet', 'Blackhole']

path_earth = ['Earth', ('Moon', 'Mars', 'Venus')]
path_venus = ['Venus', ('Blackhole',)]
path_mercury = ['Mercury', ('Sun', 'Mars', 'Comet')]
path_mars = ['Mars', ('Jupiter', )]
path_jupiter = ['Jupiter', ('Saturn',)]
path_saturn = ['Saturn', ('Neptune',)]
path_neptune = ['Neptune', ('Uranus',)]
paths = [path_earth, path_venus, path_mercury, path_mars, path_jupiter, path_saturn, path_neptune]

# ----- Creating the Graph
my_graph = Graph(nodes_list)
for path in paths:
    my_graph.create_graph(path)
my_graph.dft_recursive('Earth')

---

2. Using A StateFul Closure

Python has first-class functions, meaning you can assign them to variables, pass them as arguments to other functions, compare them in expressions, etc.

A Closure is a function object that remembers values in enclosing scopes even if they are not present in memory, you can see it be implemented in the stateful_closure function.

class Graph:

    def __init__(self, nodes: list):
        self.nodes = {node: [] for node in nodes}

    def create_graph(self, paths: list):
        node_from, nodes_to = paths
        if node_from in self.nodes:
            for node in nodes_to:
                self.nodes[node_from].append(node)
                self.nodes[node].append(node_from)
        else:
           print('Error while creating Graph, an unknown node was entered :(')


    def dft_recursive(self, starting_vertex):
        """Depth First Search using a stateful closure to keep track of Visited Node"""

        visited_nodes = set()

        def stateful_closure(starting_vertex):
            """Recursive stateful Closure function"""

            visited_nodes.add(starting_vertex)  # FAQ: This is a Closure
            starting_vertex_name = starting_vertex
            starting_vertex = self.nodes[starting_vertex]

            for neighbor in starting_vertex:
                if neighbor not in visited_nodes:
                    visited_nodes.add(neighbor)

                    if not all([bool(node in visited_nodes) for node in self.nodes[neighbor]]):
                        print(starting_vertex_name, end=' --> ')
                        stateful_closure(neighbor)
                    else:
                        print(starting_vertex_name, '--> ', neighbor, '| ')
                        continue

        stateful_closure(starting_vertex)    

# Same as prev function, shorted form to save space
nodes_list = ['Earth', 'Moon', 'Mars', 'Venus',
              'Mercury', 'Jupiter', 'Saturn',
              'Neptune', 'Uranus', 'Sun', 'Comet', 'Blackhole']
paths = [['Earth', ('Moon', 'Mars', 'Venus')],  ['Venus', ('Blackhole',)],  ['Mercury', ('Sun', 'Mars', 'Comet')],
         ['Mars', ('Jupiter', )], ['Jupiter', ('Saturn',)], ['Saturn', ('Neptune',)], ['Neptune', ('Uranus',)]]

# ----- Creating the Graph
my_graph = Graph(nodes_list)
for path in paths:
    my_graph.create_graph(path)

my_graph.dft_recursive('Earth')

---

Documentation | Guides | Other StackOverflow answers

• Can a Python function remember its previous outputs?
• Closures