들어가기 전에
2021/02/24 - [Algorithm/자료구조] - [자료구조] 그래프
그래프 탐색
- 그래프의 가장 기본적인 연산
- 시작 정점부터 차례대로 모든 정점들을 한 번씩 방문
- 많은 문제들이 단순히 탐색만으로 해결됨 ex) 도로망(특정 도시에서 다른 도시로 갈 수 있는지 여부 , 전자회로(특정 단자와 다른 단자의 연결 여부
- 깊이 우선 탐색(DFS)
- 너비 우선 탐색(BFS)
깊이 우선 탐색(DFS)
- 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행
- 되돌아가기 위해서는 스택 필요
- 순환함수 호출로 묵시적인 스택 이용
-DFS 알고리즘
- 구현1 : 인접행렬
#include <iostream>
#include <vector>
using namespace std;
int N=5;
vector<vector<int> > map(1001, vector<int>(1001, 0));
vector<bool> visited(1001); //false로 초기화
void DFS(int start) {
visited[start] = true; //현재 정점을 방문함
cout << start << " "; //현재 정점 출력
for (int i = 0; i < N; i++) {
if (!visited[i] && map[start][i]) { //연결+방문하지 않으면
DFS(i); //순환호출로 방문
}
}
}
int main() {
map[0][1]=1; //1은 연결됨, 0은 연결되지 않음(0으로 초기화를 해서 연결된 것만 고려하면 된다)
map[1][0]=1; //map[정점][정점]=1(연결) , 무방향그래프이므로 행열을 바꿔서 1을 넣어준다.
map[1][2]=1;
map[2][1]=1;
map[0][2]=1;
map[2][0]=1;
map[2][3]=1;
map[3][2]=1;
map[3][4]=1;
map[4][3]=1;
map[2][4]=1;
map[4][2]=1;
DFS(0); //시작 정점
return 0;
}
출력 결과 : 0 1 2 3 4
-구현2 : 인접 리스트
int visited[MAX_VERTICES];
// 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_list(GraphType* g, int v)
{
GraphNode* w;
visited[v] = TRUE; // 정점 v의 방문 표시
cout << v << " "; // 방문한 정점 출력
for (w = g->adj_list[v]; w; w = w->link)// 인접 정점 탐색
if (!visited[w->vertex])
dfs_list(g, w->vertex); //정점 w에서 DFS 새로 시작
}
너비 우선 탐색 (BFS)
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
- 큐를 사용하여 구현됨
-BFS 알고리즘
- 구현1 : 인접행렬
#include <iostream>
#include <vector>
using namespace std;
int N=5;
vector<vector<int> > map(1001, vector<int>(1001, 0));
vector<bool> visited(1001); //false로 초기화
void BFS(int start) {
queue<int> q;
visited[start] = true; //현재 정점을 방문함
q.push(start); //시작 정점을 큐에 저장
while (!q.empty()) {
int ver = q.front();
q.pop();
cout << ver << " "; //정점 출력
for (int i = 1; i <= N; i++) {
if (!visited[i] && map[ver][i]) {
q.push(i);
visited[i] = true;
}
}
}
}
int main() {
//A:1, B:2, C:3, D:4, E:5, F:6
//A,C
map[1][3]=1; //1은 연결됨, 0은 연결되지 않음(0으로 초기화를 해서 연결된 것만 고려하면 된다)
map[3][1]=1; //map[정점][정점]=1(연결) , 무방향그래프이므로 행열을 바꿔서 1을 넣어준다.
//A,E
map[1][5]=1;
map[5][1]=1;
//C,D
map[3][4]=1;
map[4][3]=1;
//B,C
map[2][3]=1;
map[3][2]=1;
//C,F
map[3][6]=1;
map[6][3]=1;
//B,F
map[2][6]=1;
map[6][2]=1;
//D,F
map[4][6]=1;
map[6][4]=1;
DFS(1); //시작 정점
return 0;
}
출력 결과 : 1 3 5 2 4 6
-구현2 : 인접리스트
void bfs_list(GraphType* g, int v)
{
GraphNode* w;
QueueType q;
init(&q); // 큐 초기 화
visited[v] = TRUE; // 정점 v 방문 표시
enqueue(&q, v); // 시작정점을 큐에 저장
while (!is_empty(&q)) {
v = dequeue(&q); // 큐에 저장된 정점 선택
cout << v << " ";
for (w = g->adj_list[v]; w; w = w->link) //인접 정점 탐색
if (!visited[w->vertex]) { // 미방문 정점 탐색
visited[w->vertex] = TRUE; // 방문 표시
enqueue(&q, w->vertex); //정점을 큐에 삽입
}
}
}
DFS와 BFS의 시간복잡도
- 주어진 정점에서 ㄱ래프의 모든 간선을 조회하며 인접여부를 판단( 정점의 수 n, 간선의 수e)
- 인접 행렬로 표현된 그래프 O(n^2)
- 인접 리스트로 표현된 그래프 O(n+e)
- 따라서, 그래프 내에 적은 숫자의 간선만을 갖는 희소그래프(그래프에서 간선의 수가 적은 그래피,완전 그래프의 반대되는 개념)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리함.
'Algorithm > 자료구조' 카테고리의 다른 글
[자료구조] Union Find (0) | 2021.03.25 |
---|---|
[자료구조] 탐색(search) (0) | 2021.03.02 |
[자료구조] 그래프 (0) | 2021.02.24 |
[자료구조] 동적 계획 (DP : Dynamic Programming) (0) | 2021.02.12 |
[c++ / STL] sort, priority queue (0) | 2021.01.30 |