Primer recorrido de amplitud (o búsqueda) para un gráfico es similar al primer recorrido de amplitud de un árbol (consulte el método 2 de esta publicación ).

El único inconveniente aquí es que, a diferencia de los árboles, los gráficos pueden contener ciclos, por lo que podemos llegar al mismo nodo nuevamente. Para evitar procesar un nodo más de una vez, utilizamos una matriz booleana visitada. Por simplicidad, se supone que todos los vértices son accesibles desde el vértice inicial. Por ejemplo, en el siguiente gráfico, comenzamos a recorrer desde el vértice 2. Cuando llegamos al vértice 0, buscamos todos los vértices adyacentes. 2 también es un vértice adyacente a 0. Si no marcamos los vértices visitados, entonces 2 se procesará nuevamente y se convertirá en un proceso sin finalización. Un primer recorrido en amplitud del siguiente gráfico es 2, 0, 3, 1.

A continuación se muestran las implementaciones de Breadth First Traversal simple desde una fuente determinada.

La implementación utiliza representación de lista de adyacencia de gráficos. STL 's contenedor de lista se utiliza para almacenar listas de nodos adyacentes y colas de nodos necesarios para el recorrido BFS.

# Python3 Program to print BFS traversal # from a given source vertex. BFS(int s) # traverses vertices reachable from s. from collections import defaultdict # This class represents a directed graph # using adjacency list representation class Graph: # Constructor def __init__(self): # Default dictionary to store graph self.graph = defaultdict(list) # Function to add an edge to graph def addEdge(self, u, v): self.graph[u].append(v) # Function to print a BFS of graph def BFS(self, s): # Mark all the vertices as not visited visited = [False] * (max(self.graph) + 1) # Create a queue for BFS queue = [] # Mark the source node as # visited and enqueue it queue.append(s) visited[s] = True while queue: # Dequeue a vertex from # queue and print it s = queue.pop(0) print(s, end=' ') # Get all adjacent vertices of the # dequeued vertex s. # If an adjacent has not been visited, # then mark it visited and enqueue it for i in self.graph[s]: if not visited[i]: queue.append(i) visited[i] = True # Driver code if __name__ == '__main__': # Create a graph given in # the above diagram g = Graph() g.addEdge(0, 1) g.addEdge(0, 2) g.addEdge(1, 2) g.addEdge(2, 0) g.addEdge(2, 3) g.addEdge(3, 3) print('Following is Breadth First Traversal' ' (starting from vertex 2)') g.BFS(2) # This code is contributed by Neelam Yadav # This code is modified by Susobhan Akhuli>

Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>

Complejidad del tiempo: O (V + E), donde V es el número de vértices en el gráfico y E es el número de aristas
Espacio Auxiliar: O(V)

Consulte el artículo completo sobre Primera búsqueda en amplitud o BFS para un gráfico ¡para más detalles!