그래프에 대한 너비 우선 탐색(BFS)

BFS(Breadth First Search) 탐색은 주어진 그래프의 모든 노드를 방문하는 데 사용되는 알고리즘입니다. 이 탐색 알고리즘에서는 하나의 노드를 선택한 다음 모든 인접 노드를 하나씩 방문합니다. 인접 정점을 모두 완료한 후, 다른 정점을 확인하기 위해 더 이동하고, 인접 정점을 다시 확인합니다.

이 알고리즘을 구현하려면 Queue 데이터 구조를 사용해야 합니다. 모든 인접 정점이 완료되면 모든 인접 정점이 대기열에 추가되고, 대기열에서 한 항목이 제거되고 해당 정점을 다시 통과하기 시작합니다.

그래프에서는 때때로 주기가 있을 수 있으므로 배열을 사용하여 노드를 이미 방문했는지 여부를 표시합니다.

입력 및 출력

입력:그래프의 인접 행렬입니다. A B C D E F A 0 1 1 1 0 0 B 1 0 0 1 1 0 C 1 0 0 1 0 1 D 1 1 1 0 1 1 E 0 1 0 1 0 1 F 0 0 1 1 1 0출력:BFS 순회:B A D E> 
알고리즘
 
bfs(꼭짓점, 시작)
 

 입력 -  정점 목록 및 시작 정점.
 

 출력 - 그래프가 연결된 경우 모든 노드를 탐색합니다.
 
먼저 모든 노드의 상태를 미방문으로 표시하고 que가 비어 있지 않은 상태에서 시작 정점을 큐에 추가하고 que에서 항목을 삭제하고 u로 설정합니다. u에 인접한 모든 정점 1에 대해 정점 u를 표시합니다 , 정점[i]이 방문하지 않은 경우 수행한 다음 정점[i]을 임시 방문으로 표시 v를 대기열에 추가 표시 done u를 완전히 방문한 것으로 표시 doneEnd
 
예
 
#include#include#define NODE 6 네임스페이스 사용 std;typedef struct node { int val; 정수 상태; //상태}노드;int 그래프[노드][노드] ={ {0, 1, 1, 1, 0, 0}, {1, 0, 0, 1, 1, 0}, {1, 0, 0 , 1, 0, 1}, {1, 1, 1, 0, 1, 1}, {0, 1, 0, 1, 0, 1}, {0, 0, 1, 1, 1, 0}};void bfs(노드 *vert, 노드 s) { 노드 u; 정수 i, j; 큐<노드>큐; for(i =0; i 
출력
 
BFS 순회:B A D E C F