C++에서 경쟁 코딩을 위해 STL을 사용하는 BFS?

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

경쟁 코딩에서는 문제를 매우 빠르게 해결해야 합니다. 우리는 이 알고리즘을 구현하기 위해 STL(Standard Library of C++)을 사용할 것입니다. 우리는 Queue 데이터 구조를 사용해야 합니다. 모든 인접 정점이 대기열에 추가되고 모든 인접 정점이 완료되면 대기열에서 한 항목이 제거되고 해당 정점을 다시 탐색하기 시작합니다.

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

Input : The Adjacency matrix of the graph.
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
Output : BFS Traversal: 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;
class node {
   public:
      int val;
      int state; //status
};
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