그래프 예시
그래프란, 연결되어있는 객체 간의 관계를 표현하는 자료구조이다
그래프 G는 (V,E)로 표시하며 여기서 V는 정점/노드를 E는 간선 또는 링크를 의미한다
이 글에서 사용할 그래프 예시는 다음과 같다
A,B,C 등과 같이 알파벳으로 표시된 부분이 V 즉, 정점/노드를 의미하고 그 사이를 잇는 E, 간선들이 존재한다
간선도 두가지 종류로 나눌 수 있는데 방향이 없는 무방향 그래프, 방향이 있는 방향 그래프가 있다
위 그림은 무방향 그래프로 (A,B)와 (B,A) 같은 의미로 표현된다
이처럼 무방향 그래프는 간선을 통해서 양방향으로 갈 수 있다
방향 그래프는 A->B 처럼 그려지는데 이는 간선을 통해 한쪽 방향으로만 갈 수 있음을 나타낸다
따라서 (A,B)와 (B,A)는 다른 의미로 표현된다
그래프 탐색 과정
1. BFS
BFS는 breadth-first search로 너비 우선 탐색을 의미한다
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문하는 탐색이다
이 탐색을 이용하기 위해서는 '큐'가 필요하다
인접한 노드를 표현해 보면
으로 표현해볼 수 있다
탐색 과정을 표현해보자면 
이다
사각형 부분은 방문 순서를 나타낸 것이다
여기서 가장 중요한 점은 한번 갔던 곳은 다시 가지 않는다는 것이다
파란색 부분 안에 있는 노드부터 탐색하고, 보라색, 하늘색 부분으로 넘어가면서 탐색을 수행한다
큐에는 앞서 들어있는 노드이면 다시 들어가지 않는데 예를 들어 노드 E의 근접 노드 부분을 보자
E에 근접해 있는 노드들은 C,F,G,H이다
E까지 탐색했을 때 큐에는 B, A, D, C, E가 큐 안에 들어있다
그리고 E의 근접 노드들을 확인했을 때 C는 이미 큐 안에 들어있으므로 또 큐에 넣지 않고 들어있지 않은 F, G, H가 큐 안에 들어오게 된다
이런 과정으로 BFS는 주로 최단거리(the shortest path)를 구할 때 이용한다
2. DFS
DFS는 depth-first search로 깊이 우선 탐색을 의미한다
한 방향으로 갈수 있을 때까지 가다가 더이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와 다른 방향으로 다시 탐색하는 것이다
이 탐색을 이용하기 위해서는 '스택'이 필요하다
위 BFS를 설명할 때와 같은 인접노드를 가지고 있지만 쉽게 편리하기 위해 조금 다르게 그려보았다
위 예시를 새로로 표현한 것인데 똑같이 B가 시작 지점이다
탐색 과정을 표현해보자면 
이다
사각형 부분은 방문 순서를 나타낸 것이다
앞의 BFS와 다른 점은 한쪽 경로로 들어가면 그 경로의 끝까지 간다는 점이다
A로 갔다가 A와 추가로 연결된 노드가 없어 다시 다른 노드가 있는 B로 올라온 다음 C로 넘어가 추가로 연결된 노드로 이어지며 탐색을 한다
또한 E, F, G, H부분에서도 F와 연결된 노드가 없으므로 다른 노드와 연결되어있는 E로 올라온 다음 G로 탐색을 이어간다
주로 미로 찾기나 cycle detection, edge clasifiction 등을 할 때 이용한다
코드
코드로 표현하기 전에 알파벳을 숫자로 정리해서 표현해보자
이것을 BFS, DFS로 구현해 볼 것이다
1. BFS
set starting point s
visted[s] = true -> s에 방문했다고 표시하고
Q push(s) -> Q에 s를 삽입하고
while( Q != empty) -> Q가 비어있지 않다면
~~ -> Q에서 s를 삭제한다 그 후 위 과정을 반복한다
으로 간단하게 표현해볼 수 있는데 이를 자세히 풀어보면
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int number = 8;
int visit[8];
vector<int> a[8];
void bfs(int start) {
queue<int> q;
q.push(start);
visit[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];
if (!visit[y]) { //방문하지 않았다면
q.push(y);
visit[y] = true;
}
}
}
}
int main(void) {
a[1].push_back(2);
a[2].push_back(1); //1과 2연결
a[2].push_back(3);
a[3].push_back(2); //2와 3연결
a[2].push_back(4);
a[4].push_back(2); //2와 4연결
a[3].push_back(5);
a[5].push_back(3); //3와 5연결
a[5].push_back(6);
a[6].push_back(5); //5와 6연결
a[5].push_back(7);
a[7].push_back(5); //5와 7연결
a[5].push_back(8);
a[8].push_back(5); //5와 8연결
bfs(2); //2부터 탐색 실행
return 0;
}이다
그리고 이것을 실행해 보면
라는 결과 값을 얻을 수 있다
2. DFS
set sratring point s -
visited[s] = true -> s에 방문했다고 표시하고
for i in adj[s] -> i가 s에 인접한 정점이라면
DFS(s) -> DFS를 수행한다
~~
으로 간단하게 표현해 볼 수 있는데 이를 자세히 풀어보면
#include <iostream>
#include <vector>
using namespace std;
int number = 8;
int visit[8];
vector<int> a[8];
void dfs(int start) {
if (visit[start]) { //방문한 경우 바로 빠져나옴
return;
}
visit[start] = true; //방문
printf("%d", start);
for (int i = 0; i < a[start].size(); i++) {
int x = a[start][i];
dfs(x);
}
}
int main(void) {
a[1].push_back(2);
a[2].push_back(1); //1과 2연결
a[2].push_back(3);
a[3].push_back(2); //2와 3연결
a[2].push_back(4);
a[4].push_back(2); //2와 4연결
a[3].push_back(5);
a[5].push_back(3); //3와 5연결
a[5].push_back(6);
a[6].push_back(5); //5와 6연결
a[5].push_back(7);
a[7].push_back(5); //5와 7연결
a[5].push_back(8);
a[8].push_back(5); //5와 8연결
dfs(2); //2부터 탐색 실행
return 0;
}
이다
그리고 이것을 실행해보면
라는 결과값을 얻을 수 있다
https://hongku.tistory.com/ 에서 도움을 받았다
BFS 관련 문제
교수님께서 수업 시간에 알려주신 문제 중에 BFS로 정렬하는 것만 풀어보도록 하자
이것을 위의 코드를 이용해서 풀어보자면
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int number = 10;
int visit[10];
vector<int> a[10];
void bfs(int start) {
queue<int> q;
q.push(start);
visit[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];
if (!visit[y]) { //방문하지 않았다면
q.push(y);
visit[y] = true;
}
}
}
}
int main(void) {
a[0].push_back(1);
a[1].push_back(0);
a[0].push_back(2);
a[2].push_back(0);
a[1].push_back(2);
a[2].push_back(1);
a[1].push_back(4);
a[4].push_back(1);
a[3].push_back(1);
a[1].push_back(3);
a[3].push_back(2);
a[2].push_back(3);
a[3].push_back(4);
a[4].push_back(3);
a[5].push_back(4);
a[4].push_back(5);
a[4].push_back(6);
a[6].push_back(4);
a[4].push_back(7);
a[7].push_back(4);
a[7].push_back(6);
a[6].push_back(7);
a[7].push_back(8);
a[8].push_back(7);
a[5].push_back(7);
a[7].push_back(5);
a[5].push_back(8);
a[8].push_back(5);
a[5].push_back(9);
a[9].push_back(5);
bfs(3); //2부터 탐색 실행
return 0;이다
이를 실행해보면
라는 값을 얻을 수 있다
