bfs 알고리즘이란 뭔가요?

Question

요즘 알고리즘을 배우고 있는데 bfs의 정의와 장단점, 쓰임새 그리고 구조가 궁금해요.

그리고 c, c++ 간단한 소스도 올려주시면 감사하겠습니다.

Answer 1

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 예시입니다.