Recorrido en anchura (BFS)

📖

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

ℹ️

La búsqueda en anchura comienza en un nodo raíz y explora todos los vecinos de este nodo antes de avanzar a los vecinos de los vecinos. Se expande uniformemente la frontera entre lo descubierto y lo no descubierto, como si fuera un anillo que vamos expandiendo, llegando a los nodos de distancia

k

solo después de haber llegado a todos los nodos a distancia

k-1

🧠 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

####################################################
# BFS - Breadth-First Search algorithm (iterative) #
####################################################


def bfs(g, fromnode):
    """
    Breadth-First Search algorithm (iterative)
    
    - g: adjacency list of the graph
    - fromnode: starting node of the path
    """
    n = len(g)                          # Graph length (number of nodes)
    visited = [False] * n               # Set of visited nodes, that haven't been on the queue yet (True=Visited, False=Not visited)
    path = []                           # Resulting array of nodes in a BFS order
    
    # Initialize the queue
    queue = [fromnode]                  # Queue of nodes pending to be visited (initialized with the initial node)
    visited[fromnode] = True            # Set the initial node as visited
    
    # Iterate over the queue
    while queue:                        # While there are nodes in the queue, iterate over those
        queue.sort()                    # Sort the queue to ensure we follow the same order every time (in this code we use lexicographic order)
        curr_node = queue.pop(0)        # Extract the first node standing on the queue
        path.append(curr_node)          # Add the node to the resulting path
        for adj in g[curr_node]:        # Iterate over the neighbours of the node
            if not visited[adj]:        # If the neighbour have never been in the queue...
                queue.append(adj)       # Add it to the queue
                visited[adj] = True     # Set the neighbour as visited

    return path, visited


################################################

if __name__ == "__main__":
    graph = [[1, 2], [0, 3, 4], [0, 5, 6], [1], [1], [2], [2], []]
    result_path, visited_nodes = bfs(graph, 0)
    print(result_path)