Pierwsze przechodzenie wszerz (lub wyszukiwanie) for graph jest podobny do pierwszego przejścia drzewa przez szerokość (patrz metoda 2 z ten post ).
Jedynym haczykiem jest to, że w przeciwieństwie do drzew, grafy mogą zawierać cykle, więc możemy ponownie dojść do tego samego węzła. Aby uniknąć wielokrotnego przetwarzania węzła, używamy tablicy odwiedzanych wartości logicznych. Dla uproszczenia zakłada się, że wszystkie wierzchołki są osiągalne z wierzchołka początkowego. Na przykład na poniższym grafie zaczynamy przechodzenie od wierzchołka 2. Kiedy dochodzimy do wierzchołka 0, szukamy wszystkich sąsiednich wierzchołków. 2 jest jednocześnie sąsiadującym wierzchołkiem 0. Jeśli nie zaznaczymy odwiedzonych wierzchołków, to 2 zostanie przetworzone ponownie i będzie to proces niekończący się. Przejście wszerz poniższego wykresu to 2, 0, 3, 1. 
Zalecane: Proszę o rozwiązanie ĆWICZYĆ najpierw, zanim przejdziemy do rozwiązania.
Poniżej znajdują się implementacje prostego przejścia wszerz z danego źródła.
Implementacja wykorzystuje reprezentacja listy sąsiedztwa wykresów. STL 'S kontener listy służy do przechowywania list sąsiadujących węzłów i kolejki węzłów potrzebnych do przejścia BFS.
Pyton # 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> Wyjście
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Złożoność czasowa: O(V+E), gdzie V to liczba wierzchołków grafu, a E to liczba krawędzi
Przestrzeń pomocnicza: O(V)
Proszę zapoznać się z pełnym artykułem na temat Wyszukiwanie wszerz lub BFS dla wykresu po więcej szczegółów!