- 큐 (queue)
https://www.youtube.com/watch?v=yAiZ1AVU8Aw&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=15
https://blog.naver.com/ndb796/221230944729
- 너비 우선 탐색 (BFS)
https://www.youtube.com/watch?v=66ZKz-FktXo&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=16
https://blog.naver.com/ndb796/221230944971
- 예제 코드
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int number = 7; // 그래프의 노드 수
int c[7]; // 방문 여부를 체크할 배열
vector<int> a[8]; // 인접 리스트를 나타내는 배열
// 너비 우선 탐색 (BFS) 함수 정의
void bfs(int start) {
queue<int> q; // 큐를 사용하여 BFS를 구현
q.push(start); // 시작 노드를 큐에 넣고 방문 표시
c[start] = true;
while (!q.empty()) {
int x = q.front(); // 큐의 맨 앞에 있는 노드를 꺼내옴
q.pop();
printf("%d ", x); // 방문한 노드 출력
// 현재 노드에 연결된 노드들을 순회
for (int i = 0; i < a[x].size(); i++) {
int y = a[x][i]; // 연결된 노드 y
// 아직 방문하지 않은 노드라면 큐에 넣고 방문 표시
if (!c[y]) {
q.push(y);
c[y] = true;
}
}
}
}
int main(void) {
// 그래프의 간선 정보를 인접 리스트에 저장
// 1과 2를 연결합니다.
a[1].push_back(2);
a[2].push_back(1);
// 1과 3를 연결합니다.
a[1].push_back(3);
a[3].push_back(1);
// 2과 3를 연결합니다.
a[2].push_back(3);
a[3].push_back(2);
// 2과 4을 연결합니다.
a[2].push_back(4);
a[4].push_back(2);
// 2과 5를 연결합니다.
a[2].push_back(5);
a[5].push_back(2);
// 3와 6을 연결합니다.
a[3].push_back(6);
a[6].push_back(3);
// 3와 7을 연결합니다.
a[3].push_back(7);
a[7].push_back(3);
// 4와 5를 연결합니다.
a[4].push_back(5);
a[5].push_back(4);
// 6과 7을 연결합니다.
a[6].push_back(7);
a[7].push_back(6);
// BFS를 시작 노드인 1에서 수행합니다.
bfs(1);
return 0;
}
'자료구조와 알고리즘 > [인강] 자료구조와 알고리즘' 카테고리의 다른 글
스택 (stack) & 깊이 우선 탐색 (DFS) (0) | 2023.10.22 |
---|