BFS란 무엇입니까?
BFS(Breadth-First Search)는 루트 노드부터 시작하는 순회 대기열에 각 노드의 이웃을 추가하여 순회 노드를 기반으로 합니다. 그래프의 BFS는 그래프에 사이클이 있을 수 있다는 점을 제외하면 트리의 BFS와 유사합니다. 깊이 우선 탐색과 달리, 다음 레벨로 진행하기 전에 주어진 깊이에 있는 모든 이웃 노드를 조사합니다.
BFS 알고리즘
다음은 그래프를 탐색하기 위해 너비 우선 검색을 사용하는 단계입니다.
- 그래프의 인접 행렬 또는 인접 목록에 대한 데이터를 가져옵니다.
- 대기열을 만들고 항목으로 채웁니다.
- 루트 노드를 활성화합니다(대기열 시작 부분에서 루트 노드를 얻는다는 의미).
- 대기열의 헤드(또는 초기 요소)를 대기열에서 빼낸 다음 대기열의 모든 근처 노드를 왼쪽에서 오른쪽으로 대기열에 넣습니다. 노드에 조사해야 할 근처 노드가 없으면 헤드를 대기열에서 빼고 작업을 재개하기만 하면 됩니다. (참고: 이전에 조사되었거나 대기열에 있는 이웃이 나타나면 대기열에 넣지 말고 건너뛰십시오.)
- 대기열이 빌 때까지 이 방식을 계속합니다.
BFS 애플리케이션
알고리즘의 유연성으로 인해 Breadth-First Search는 실제 세계에서 매우 유용합니다. 다음은 그 중 일부입니다:
- P2P 네트워크에서는 피어 노드가 검색됩니다. BitTorrent, uTorrent 및 qBittorent와 같은 대부분의 토렌트 클라이언트는 이 프로세스를 사용하여 네트워크에서 '시드'와 '피어'를 찾습니다.
- 인덱스는 웹 크롤링의 그래프 탐색 기술을 사용하여 구축됩니다. 절차는 소스 페이지를 루트 노드로 시작하여 소스 페이지에 연결된 모든 보조 페이지까지 진행됩니다(이 프로세스는 계속됩니다). 재귀 트리의 깊이가 줄어들기 때문에 너비 우선 검색은 여기서 본질적인 이점을 갖습니다.
- GPS를 사용하는 GPS 내비게이션 시스템을 사용하면 너비 우선 검색을 수행하여 인근 사이트를 찾습니다.
- 너비우선탐색(breadth-first search) 개념을 채용한 체니(Cheney)의 기법은 가비지 수집에 사용된다.
BFS 순회 예
시작하려면 간단한 예를 살펴보겠습니다. 루트 노드로 0부터 시작하여 그래프 아래로 진행해 보겠습니다.
역참조 포인터 c
1 단계: 대기열에 넣기(0)
대기줄
| 0 |
2 단계: 큐에서 빼기(0), 큐에 넣기(1), 큐에 넣기(3), 큐에 넣기(4)
대기줄
| 1 | 삼 | 4 |
3단계: 큐에서 빼기(1), 큐에 넣기(2)
자바 인스턴스화
대기줄
| 삼 | 4 | 2 |
4단계: 큐에서 빼기(3), 큐에 넣기(5). 0이 이미 탐색되었으므로 대기열에 1을 다시 추가하지 않습니다.
대기줄
| 4 | 2 | 5 |
5단계: 대기열에서 제거(4)
대기줄
의도 의도
| 2 | 5 |
6단계: 대기열에서 제거(2)
대기줄
이진 트리 자바
| 5 |
7단계: 대기열에서 제거(5)
대기줄
이제 대기열이 비어 있으므로 프로세스를 중지하겠습니다.
너비 우선 검색 Java 프로그램
코드를 다루는 방법에는 여러 가지가 있습니다. 우리는 주로 Java에서 너비 우선 검색을 구현하는 단계에 대해 논의할 것입니다. 인접 목록이나 인접 행렬을 사용하여 그래프를 저장할 수 있습니다. 어느 방법이든 허용됩니다. 인접 목록은 코드에서 그래프를 나타내는 데 사용됩니다. Java에서 Breadth-First Search 알고리즘을 구현할 때 노드가 헤드(또는 시작)에서 대기열에서 제외되면 각 노드에 연결된 노드 목록을 통해서만 이동하면 되므로 인접 목록을 처리하는 것이 훨씬 쉽습니다. 대기줄.
코드를 시연하는 데 사용된 그래프는 이전 예에서 사용된 그래프와 동일합니다.
BFSTraversal.java
import java.io.*; import java.util.*; public class BFSTraversal { private int node; /* total number number of nodes in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { node = v; adj = new LinkedList[node]; for (int i=0; i<v; i++) { adj[i]="new" linkedlist(); } que="new" void insertedge(int v,int w) adj[v].add(w); * adding an edge to the adjacency list (edges are bidirectional in this example) bfs(int n) boolean nodes[]="new" boolean[node]; initialize array for holding data int a="0;" nodes[n]="true;" que.add(n); root node is added top of queue while (que.size() !="0)" n="que.poll();" remove element system.out.print(n+' '); print (int i="0;" < adj[n].size(); iterate through linked and push all neighbors into if (!nodes[a]) only insert nodes they have not been explored already nodes[a]="true;" que.add(a); public static main(string args[]) bfstraversal graph="new" bfstraversal(6); graph.insertedge(0, 1); 3); 4); graph.insertedge(4, 5); graph.insertedge(3, graph.insertedge(1, 2); 0); graph.insertedge(2, graph.insertedge(5, system.out.println('breadth first traversal is:'); graph.bfs(0); pre> <p> <strong>Output:</strong> </p> <pre> Breadth First Traversal for the graph is: 0 1 3 4 2 5 </pre> <hr></v;>