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 C F
알고리즘
bfs(정점, 시작)
입력 − 정점 목록 및 시작 정점.
출력 − 그래프가 연결된 경우 모든 노드를 순회합니다.
Begin define an empty queue que at first mark all nodes status as unvisited add the start vertex into the que while que is not empty, do delete item from que and set to u display the vertex u for all vertices 1 adjacent with u, do if vertices[i] is unvisited, then mark vertices[i] as temporarily visited add v into the queue mark done mark u as completely visited done End
예
#include<iostream>
#include<queue>
#define NODE 6
using namespace std;
typedef struct node{
int val;
int state; //status
}node;
int graph[NODE][NODE] = {
{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(node *vert, node s){
node u;
int i, j;
queue<node> que;
for(i = 0; i<NODE; i++){
vert[i].state = 0; //not visited
}
vert[s.val].state = 1;//visited
que.push(s); //insert starting node
while(!que.empty()){
u = que.front(); //delete from queue and print
que.pop();
cout << char(u.val+'A') << " ";
for(i = 0; i<NODE; i++){
if(graph[i][u.val]){
//when the node is non-visited
if(vert[i].state == 0){
vert[i].state = 1;
que.push(vert[i]);
}
}
}
u.state = 2;//completed for node u
}
}
int main(){
node vertices[NODE];
node start;
char s;
for(int i = 0; i<NODE; i++){
vertices[i].val = i;
}
s = 'B';//starting vertex B
start.val = s-'A';
cout << "BFS Traversal: ";
bfs(vertices, start);
cout << endl;
} 출력
BFS Traversal: B A D E C F