그래프의 너비 우선 검색은 레벨별로 정점을 방문합니다. 첫 번째 수준은 시작 정점으로 구성됩니다. 다음 각 레벨은 이전 레벨의 정점에 인접한 정점으로 구성됩니다. 그래프의 너비 우선 순회는 트리 순회에서 설명한 트리의 너비 우선 순회와 같습니다. 트리의 너비 우선 순회를 사용하면 노드가 수준별로 방문됩니다. 먼저 루트를 방문한 다음 루트의 모든 자식, 루트의 손자 등을 방문합니다. 마찬가지로, 그래프의 너비 우선 검색은 먼저 정점을 방문한 다음 모든 인접한 정점, 그런 다음 해당 정점에 인접한 모든 정점 등을 방문합니다. 각 정점이 한 번만 방문되도록 하기 위해 이미 방문한 정점은 건너뜁니다.
그래프의 꼭짓점 v부터 시작하는 너비 우선 검색 알고리즘은 아래 코드에 설명되어 있습니다.
입력: G = (V, E) 및 시작 정점 v
출력: v
에 뿌리를 둔 BFS 트리 1 트리 bfs(정점 v) {
2 방문할 정점을 저장하기 위한 빈 대기열을 만듭니다.
3 대기열에 v를 추가합니다.
4 마크 v 방문;
5
6 while(큐가 비어 있지 않음) {
7 큐에서 꼭지점(예: u)을 큐에서 제거합니다.
8 탐색된 정점 목록에 u를 추가합니다.
당신의 이웃 w당 9
w를 방문하지 않은 경우 10 {
11 대기열에 w를 추가하세요.
12 트리에서 u를 w의 부모로 설정합니다.
13시 방문;
14 }
15 }
16 }
아래 그림 (a)의 그래프를 살펴보세요. 정점 0에서 너비 우선 검색을 시작한다고 가정합니다. 아래 그림 (b)에 표시된 대로 먼저 0을 방문한 다음 모든 이웃인 1, 2, 3을 방문합니다. 정점 1에는 0, 2, 4라는 세 개의 이웃이 있습니다. 0과 2는 이미 방문했으므로 아래 그림(c)에 표시된 것처럼 이제 4만 방문합니다. 정점 2에는 0, 1, 3이라는 세 개의 이웃이 있으며 모두 방문되었습니다. 정점 3에는 0, 2, 4라는 세 개의 이웃이 있으며 모두 방문했습니다. 정점 4에는 두 개의 이웃 1과 3이 있으며 모두 방문되었습니다. 이로써 검색이 종료됩니다.
각 모서리와 각 꼭지점은 한 번만 방문하므로bfs방법의 시간 복잡도는O(|E| + |V|)입니다. 여기서|E|는 모서리 수를 나타내고|V는 |정점의 수
bfs(int v)메소드는Graph인터페이스에 정의되고 AbstractGraph.java 클래스(197-222행)에 구현됩니다. 정점 v를 루트로 사용하여Tree클래스의 인스턴스를 반환합니다. 이 메서드는 검색된 정점을 목록searchOrder(198행)에 저장하고 배열parent(199행)에 있는 각 정점의 부모이며 대기열에 연결된 목록을 사용하고(203-204행)isVisited정점을 방문했는지 여부를 나타내는 배열(라인 207) 검색은 정점v부터 시작됩니다.v는 206행의 대기열에 추가되고 방문한 것으로 표시됩니다(207행). 이제 이 메서드는 대기열(라인 210)의 각 정점u을 검사하고 이를searchOrder(라인 211)에 추가합니다. 이 메서드는u의 방문하지 않은 각 이웃e.v을 대기열에 추가하고(라인 214), 상위 항목을u(라인 215)로 설정하고, 이를 방문한 것으로 표시합니다(라인 216).
아래 코드는 시카고에서 시작하여 위 그림의 그래프에 대한 BFS를 표시하는 테스트 프로그램을 제공합니다.
12개의 정점이 다음 순서로 검색됩니다.
시카고 시애틀 덴버 캔자스시티 보스턴 뉴욕
샌프란시스코 로스앤젤레스 애틀랜타 달라스 마이애미 휴스턴
시애틀의 부모는 시카고
샌프란시스코의 부모는 시애틀입니다
로스앤젤레스의 부모는 덴버입니다
덴버의 부모는 시카고입니다
캔자스시티의 부모는 시카고입니다
보스턴의 부모는 시카고
뉴욕의 부모는 시카고
애틀랜타의 부모는 캔자스 시티
마이애미의 부모는 애틀랜타입니다
달라스의 부모는 캔자스시티입니다
휴스턴의 부모는 애틀랜타입니다
DFS로 해결된 많은 문제는 BFS를 사용해도 해결할 수 있습니다. 특히 BFS는 다음 문제를 해결하는 데 사용될 수 있습니다.
以上是廣度優先搜尋 (BFS)的詳細內容。更多資訊請關注PHP中文網其他相關文章！
