그래프를 표현하는 방법에는 크게 두가지가 있다.
첫번째는 인접행렬이고, 두번째는 인접리스트이다.
전자는 정점이 N개라면 N * N 만큼의 메모리가 필요하며, (2차원 배열)
후자는 간선의 개수만큼의 메모리만 필요하다. (연결 리스트)
그러나 탐색관점에서 본다면
전자의 경우는 A라는 정점에 연결된 여러개의 정점들에 바로 접근 할 수 있지만, (인덱스를 통해)
후자의 경우는 리스트이기 때문에 그렇게 할 수는 없다. (list->next->next...)
그래서 메모리와 탐색 측면에서 그래프를 표현하는 방법으로
C++의 vector를 이용 할 수 있다.
vector의 push_back을 이용하여 아래와 같은 형태의 그래프를 표현 할 수 있다.
V Adj
----------
A ->[][]
B ->[][][]
C ->[]
----------
물론 push_back 시 메모리 공간 재할당 및 값의 복사는 매번 발생하겠지만, 그래프가 완성 된 후에는
인접행렬과 인접리스트의 장점을 모두 갖는 다고 볼 수 있기에 매력적인 방법인 것 같다.
그래프와 관련된 여러가지 알고리즘이 있다. 다익스트라, 프림, 크루스칼, 벨만포드 와 같은 최단 경로 및 최소신장트리를 찾는 방법과
그래프 자체를 순회하는 깊이우선탐색, 너비우선탐색 있다.
여기서는 DFS, BFS의 구현에 대해 살펴보겠다.
사용한 그래프의 형태는 아래와 같다.
0
↙ ↘
1 3 -> 2
↕
4
화살표 모양이지만 무방향 그래프라 보면 된다.
static void dfs(list<int> * graph, int v, int start)
{
stack<int> s;
int * visit = new int[v];
memset(visit, 0, sizeof(int) * v);
s.push(start);
while (!s.empty())
{
int cur = s.top();
s.pop();
cout << cur << " -> "; //test
visit[cur] = 1;
list<int> &adj = graph[cur];
for (list<int>::iterator itr = adj.begin();
itr != adj.end(); itr++)
{
if (!visit[*itr])
s.push(*itr);
}
}
cout << "fin" << endl;
}v는 정점의 개수이다.
DFS는 방문할 정점으로부터 한 우물만 파는 식이므로, 스택이 사용된다.
그래서 그 출력 결과는 아래와 같다.
0 -> 3 -> 2 -> 4 -> 1 -> fin
static void bfs(list<int> * graph, int v, int start)
{
queue<int> q;
int * visit = new int[v];
memset(visit, 0, sizeof(int) * v);
q.push(start);
while (!q.empty())
{
int cur = q.front();
q.pop();
cout << cur << " -> ";
visit[cur] = 1;
list<int> &adj = graph[cur];
for (list<int>::iterator itr = adj.begin();
itr != adj.end(); itr++)
{
if (!visit[*itr])
q.push(*itr);
}
}
cout << "fin" << endl;
}bfs 인접한 정점들 부터 먼저 방문하기 때문에 큐가 사용된다.
같은 그래프에 대해서 출력 결과는 아래와 같다.
0 -> 1 -> 3 -> 2 -> 4 -> fin
끝으로 dfs와 bfs를 구현한 코드 패턴을 보면 사용된 자료구조의 차이만 존재 할 뿐 그외에 차이점은 없다.
방문할 순서를 어떻게 할 것인가에 차이만 존재 할 뿐이다.