幅優先トラバーサル (または検索) グラフの場合、ツリーの幅優先走査に似ています (方法 2 を参照) この郵便受け ）。
ここでの唯一の注意点は、ツリーとは異なり、グラフにはサイクルが含まれる可能性があるため、同じノードに再び到達する可能性があることです。ノードを複数回処理することを避けるために、ブール値の訪問済み配列を使用します。簡単にするために、すべての頂点が開始頂点から到達可能であると仮定します。たとえば、次のグラフでは、頂点 2 からトラバースを開始します。頂点 0 に到達したら、その頂点に隣接するすべての頂点を探します。 2 は 0 の隣接頂点でもあります。訪問した頂点をマークしないと、2 が再度処理され、非終了プロセスになります。次のグラフの幅優先トラバーサルは 2、0、3、1 です。 
Java 演算子推奨: で解決してください 練習する 解決策に進む前に、まず。
以下は、特定のソースからの単純な幅優先トラバーサルの実装です。
実装では使用します 隣接リスト表現 グラフの。 STL の リストコンテナ 隣接ノードのリストと 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>
時間計算量 : O(V+E)、V はグラフの頂点の数、E はエッジの数です。
補助スペース: O(V)
完全な記事を参照してください グラフの幅優先検索または BFS 詳細については！