너비 우선 검색을 위한 Python 프로그램 또는 그래프를 위한 BFS
너비 우선 순회(또는 검색) 그래프의 경우 트리의 너비 우선 순회와 유사합니다(방법 2 참조). 이 게시물 ).
여기서 유일한 문제는 트리와 달리 그래프에 사이클이 포함될 수 있으므로 동일한 노드에 다시 올 수 있다는 것입니다. 노드를 두 번 이상 처리하지 않으려면 부울 방문 배열을 사용합니다. 단순화를 위해 시작 정점에서 모든 정점에 도달할 수 있다고 가정합니다. 예를 들어, 다음 그래프에서는 정점 2에서 순회를 시작합니다. 정점 0에 도달하면 인접한 모든 정점을 찾습니다. 2도 0의 인접한 정점입니다. 방문한 정점을 표시하지 않으면 2가 다시 처리되어 비종료 프로세스가 됩니다. 다음 그래프의 너비 우선 순회는 2, 0, 3, 1입니다. 
다음은 주어진 소스에서 간단한 Breadth First Traversal의 구현입니다.
구현에서는 인접 목록 표현 그래프의. 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는 가장자리 수입니다.
보조 공간: 오(V)
전체 기사를 참조하세요. 그래프의 너비 우선 검색(BFS) 상세 사항은!
