Перший обхід у ширину (або пошук) для графа подібний до першого обходу дерева в ширину (див. метод 2 цей пост ).
Єдина заковика тут полягає в тому, що на відміну від дерев, графи можуть містити цикли, тож ми можемо знову прийти до того самого вузла. Щоб уникнути обробки вузла більше одного разу, ми використовуємо булевий відвіданий масив. Для простоти передбачається, що всі вершини досяжні з початкової вершини. Наприклад, у наступному графі ми починаємо обхід з вершини 2. Коли ми приходимо до вершини 0, ми шукаємо всі суміжні з нею вершини. 2 також є суміжною вершиною 0. Якщо ми не позначаємо відвідані вершини, тоді 2 буде оброблено знову, і це стане незавершеним процесом. Перший обхід у ширину наступного графіка дорівнює 2, 0, 3, 1. 
Рекомендовано: розв’яжіть це на ПРАКТИКА спочатку, перш ніж перейти до рішення.
Нижче наведено реалізації простого обходу спочатку в ширину з заданого джерела.
Реалізація використовує представлення списку суміжності графіків. STL 's контейнер списку використовується для зберігання списків суміжних вузлів і черги вузлів, необхідних для обходу BFS.
Python # 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)
підготуватися до тесту mockito
Перегляньте повну статтю Пошук спочатку в ширину або BFS для графіка для більш детальної інформації!