Recorrido en profunidad (DFS)

📖

La búsqueda en profundidad (también conocida como DFS, Depth First Search) sirve para recorrer los nodos un grafo a partir de un nodo inicial

ℹ️

Este algoritmo consiste en ir recorriendo los nodos y sus nodos adyacentes de forma recursiva. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado

🧠 Complejidad → $O(n)$
Siendo $n$ → $max(V,E)$ el valor máximo entre el número de vertices y el número de aristas

⚠️

Como cualquier recorrido, si el grafo es no conexo, el recorrido solo contendrá los nodos de la misma componente conexa

##################################################
# DFS - Depth First Search algorithm (recursive) #
##################################################


def dfs_recursive(g, visited, node, result):
    """
    Recursive function for DFS algorithm
    """
    result.append(node)                                 # Add the node to the path
    for adj in g[node]:                                 # Iterate over the neighbours of the node
        if adj not in visited:                          # If those haven't been visited yet, visit them
            visited.add(adj)                            # Add the neighbour to the visited set
            dfs_recursive(g, visited, adj, result)      # Make a recursive call for every neighbour


def dfs(g, fromnode):
    """
    Depth First Search algorithm preparation function

    - g: adjacency list of the graph
    - fromnode: starting node of the path
    """
    result = []                                         # The resulting path due to the DFS algorithm
    visited = set()                                     # Set of visited nodes (node has been already handled by a recursive call)
    n = len(g)                                          # Length of the graph (number of nodes)
    
    dfs_recursive(g, visited, fromnode, result)         # Make the initial recursive call
        
    return result, visited


#########################################
if __name__ == "__main__":
    graph = [[1, 2], [0, 3, 4], [0, 5, 6], [1], [1], [2], [2], []]
    path, visited = dfs(graph, 0)
    print(path, visited)