[알고리즘 - 이론] 그래프의 탐색 (DFS, BFS)
한 정점에서 시작하여 연결된 모든 정점을 한번씩 방문하는 방법
1. DFS (깊이 우선 탐색)
- 재귀 호출을 이용한 구현
void dfs(int x){
check[x] = true;
for (int i = 0; i <a[x].size(); i++){
int y = a[x][i];
if (check[i] == false) {
dfs(y);
}
}
}
O(V^2)[인접행렬] -> O(V+E) [인접리스트] 으로 단축!
2. BFS (너비 우선 탐색)
- queue를 이용한 구현
queue<int> q;
check[1] = true;
q.push(1);
while(!q.empty) {
int x = q.front(); q.pop();
for (int i = 0; i < a[x].size(); i++){
int y = a[x][i];
if (check[y] == false) {
check[y] = true; q.push(y);
}
}
3. DFS 과 BFS
bool check[1001];
vector<int> a[1001];
void dfs(int node) {
check[node] = true;
cout << node << " ";
for (int i = 0; i < a[node].size(); i++) {
int next = a[node][i];
if (check[next] == false) {
dfs(next);
}
}
}
void bfs(int start) {
queue<int> q;
memset(check, false, sizeof(check));
check[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front(); q.pop();
cout << node << " ";
for (int i = 0; i < a[node].size(); i++) {
int next = a[node][i];
if (check[next] == false) {
check[next] = true;
q.push(next);
}
}
}
}
int main() {
int n, m, start;
cin >> n >> m >> start;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
sort(a[i].begin(), a[i].end()); //a[i] inner sorting
}
dfs(start);
cout << "\n";
bfs(start);
cout << "\n";
return 0;
}
- 기억할 점
-
Vector 내를 정렬하고 싶은 경우
: sort(a[i].begin(), a[i].end()) -
배열을 초기화 하고 싶은 경우
: memset(check, false, sizeof(check))
Author And Source
이 문제에 관하여([알고리즘 - 이론] 그래프의 탐색 (DFS, BFS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@soddong/알고리즘-이론-그래프의-탐색-DFS-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)