DFS & BFS
DFS
•
시작점부터 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하고 넘어가는 방법
[재귀함수]나 [스택]으로 구현
1.
탐색 시작 노드를 스택에 삽입하고 방문처리
2.
스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문처리, 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다
3.
2번의 과정을 수행할 수 없을 때까지 반복
•
노드 방문 시 방문(visited) 여부를 반드시 검사해야 한다. 아니면 무한루프에 빠질 수 있다
•
탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 제한(depth bound)를 사용
•
깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면, 최근에 첨가된 노드의 부모노드로 돌아와서(백트래킹-backtracking), 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성
장점
•
단지 현 경로상의 노드만을 기억하면 되므로, 저장공간의 수요가 비교적 적다
•
목표노드가 깊은 단계에 있을 경우, 해를 빨리 구할 수 있다
단점
•
해가 없는 경로에 깊이 빠질 가능성이 있다.
•
따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고, 목표노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수도 있다
•
얻어진 해가 최단 경로가 된다는 보장이 없다.
•
이는 목표에 이르는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수도 있다
알고리즘
void dfs(int x) {
visited[x] = true;
cout << x << " ";
for (int i = 0; i < graph[x].size(); i++) { // 인접한 노드 사이즈만큼 탐색
int y = graph[x][i];
if (!visited[y]) {
// 방문하지 않았으면 즉, visited가 false일 때, not을 해주면 true가 되므로 아래 dfs 실행
dfs(y); // 재귀적으로 방문
}
}
}
C++
복사
BFS
•
시작 노드를 방문한 후, 시작 노드에 있는 인접한 모든 노드들을 우선 탐색
◦
최단 경로 탐색 or 임의의 경로 탐색
•
더이상 방문하지 않은 노드가 없을 때까지 방문하지 않은 모든 노드에 대해서도 BFS를 적용한다
[큐]를 이용하여 구현
그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘
1.
탐색 시작 노드를 큐에 삽입하고 방문 처리
2.
큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리
3.
2번 반복
→ 특정 조건의 최단 경로 알고리즘을 계산할 때 사용
장점
•
출발노드에서 목표노드까지의 최단 길이 경로를 보장
단점
•
경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간이 필요
•
해가 존재하지 않는다면, 유한그래프의 경우 모든 그래프를 탐색한 후에 실패로 끝난다
•
무한그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다
알고리즘
void bfs(int start) {
queue<int> q;
q.push(start); // 첫 노드를 queue에 삽입
visited[start] = true; // 첫 노드를 방문 처리
// 큐가 빌 때까지 반복
while (!q.empty()) {
// 큐에서 하나의 원소를 뽑아 출력
int x = q.front();
q.pop();
cout << x << " ";
// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for (int i = 0; i < graph[x].size(); i++) {
int y = graph[x][i];
if (!visited[y]) {
q.push(y);
visited[y] = true;
}
}
}
}
C++
복사
그래프 표현 방식
1. 인접 행렬 : 2차원 배열로 그래프 표현
[i]에서 [j] 방향으로 연결 되어 있으면 1, 아니면 0 처리
장점
•
구현 쉽다
•
연결 여부 확인하기 용이
•
arr[i][j]가 1인지 0인지만 알면 된다
단점
•
노드 [i]와 연결된 모든 노드들에 방문해보고 싶을 때, arr[i][1]부터 arr[i][전체노드개수]를 모두 확인해봐야하기 때문에 시간복잡도가 크다
2. 인접 리스트 : 리스트로 그래프 표현
•
인접리스트는 그래프의 연결 리스트의 자료구조를 이용하여 구현
◦
c++에선 vector를 사용하여 구현
•
arr[i] : 노드 i에 연결된 노드들을 원소로 같는 리스트
