그림 설명, BFS 알고리즘을 구현하기 위한 Python 코드와 함께 BFS 알고리즘의 원리에 대한 심층 분석입니다.

폭 우선 검색이라고도 알려진 BFS는 DFS 알고리즘과 같은 재귀 알고리즘입니다. 차이점은 BFS 알고리즘은 루프를 피하면서 모든 대상 노드를 순회한다는 것입니다.

BFS 알고리즘의 작동 원리 설명

아래와 같이 5개의 노드가 있는 무방향 그래프를 예로 들어 보겠습니다.

노드 0부터 시작하여 BFS 알고리즘은 먼저 이를 방문 목록에 넣습니다. 그리고 그들 모두 이웃 노드가 대기열에 들어갑니다.

다음으로 대기열 앞의 노드 1을 방문하여 노드 1에 인접한 노드로 이동합니다. 노드 0은 이미 방문했으므로 노드 2를 방문합니다.

노드 2에는 방문하지 않은 이웃 노드 4가 있지만 노드 4가 대기열 끝에 있기 때문에 대기열 앞의 노드 3을 먼저 방문하려고 합니다.

방문하지 않은 큐에는 노드 4만 남으므로 노드 4가 마지막으로 방문됩니다.

이 시점에서 이 무방향 그래프의 너비 우선 순회가 완료되었습니다.

BFS 알고리즘의 의사 코드

create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
remove the head u of Q 
mark and enqueue all (unvisited) neighbours of u

BFS 알고리즘을 구현하는 Python 코드

import collections
def bfs(graph, root):
    visited, queue = set(), collections.deque([root])
    visited.add(root)

while queue:
        vertex = queue.popleft()
        print(str(vertex) + " ", end="")

        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

if __name__ == '__main__':
    graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
    print("Following is Breadth First Traversal: ")
    bfs(graph, 0)

위 내용은 그림 설명, BFS 알고리즘을 구현하기 위한 Python 코드와 함께 BFS 알고리즘의 원리에 대한 심층 분석입니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!