bfs 알고리즘이란 뭔가요?

Question

요즘 알고리즘을 배우고 있는데 bfs의 정의와 장단점, 쓰임새 그리고 구조가 궁금해요.그리고 c, c++ 간단한 소스도 올려주시면 감사하겠습니다.

프알못 · Accepted Answer

BFS는 그래프를 탐색하는 방법 중 하나입니다.Breadth-First Search, 너비 우선 탐색이라는 뜻인데요,루트 노드(나 임의의 노드)부터 시작해서 가까운 노드부터 탐색합니다.가까운 노드부터 탐색하기 위해 포기해야 할 게 있습니다. (단점)재귀적으로 동작하지 않습니다. (좀... 직관적이지 않습니다.)노드 방문 여부를 반드시 검사해야 합니다. (적당히 처리를...)가까운 노드부터 탐색하는 게 유리한 경우에 사용하는 알고리즘입니다. (쓰임새)typedef struct _node { // BFS 구조...?
  int visited; // 방문 여부를 검사해야 합니다. 편의상 노드에 넣었습니다.
  int neighbor; // malloc(sizeof(struct _node) + sizeof(Node) * n)
  struct _node *neighbors[]; // 길이가 neighbor인, 이웃 노드 배열
} *Node;

typedef struct _node_queue *NodeQueue; // 큐는 생략합니다.
NodeQueue new_NodeQueue(); // 큐를 이렇게 만들 수 있고,
void delete_NodeQueue(NodeQueue q); // 이렇게 없앨 수 있고
bool NodeQueue_empty(NodeQueue q); // 그 외에 empty나
void NodeQueue_enqueue(NodeQueue q, Node node); // enqueue나
Node NodeQueue_dequeue(NodeQueue q); // dequeue같은 게 있다고 치죠!

// visit이 true를 반환하면 탐색을 그만둡니다.
void bfs(Node root, bool (*visit)(Node node)) {
  static int seq = 0; // 한 번 호출할 때마다 1씩 증가할 변수입니다.
  seq++; // Node->visited 매번 초기화하기 귀찮아서(...) 만들었습니다.
  NodeQueue q = new_NodeQueue(); // BFS는 보통 큐를 사용합니다.
  NodeQueue_enqueue(q, root); // 루트 노드를 넣고 시작합니다.
  while(!NodeQueue_empty(q)) { // 큐가 비워지면 탐색을 마친 것입니다.
    Node curr = NodeQueue_dequeue(q); // 이번에 처리할 노드입니다.
    if((*visit)(curr)) break; // 일단 노드를 방문합니다. (적절한 처리)
    for(int i = 0; i < curr->neighbor; i++) { // 그 노드의 이웃을
      if(curr->neighbors[i]->visited != seq) { // 아직 방문하지 않았다면
        NodeQueue_enqueue(q, curr->neighbors[i]); // 큐에 넣고
        curr->neighbors[i]->visited = seq; // 방문했다는 걸 기록해둡니다.
      }
    } // ※ 주의사항: 이 함수는 그냥 예시일 뿐입니다. 참고만 해 주세요!
  } // 이 함수를 int의 범위만큼 호출하면 정상 동작을 보장하지 않습니다.
  delete_NodeQueue(q);
}C 간단한 bfs 예시입니다.

생활꿀팁

생활꿀팁

bfs 알고리즘이란 뭔가요?