[Data structure, C++, C#] 그래프 개념 및 표현 그리고 그래프 순회

5 minute read

그래프

설명을 할 때는 간편히 C#을 사용했지만, 실제 구현 내용은 C++로 구현하였습니다.

1. 그래프의 개념

현실 세계의 사물이나 추상적인 개념간의 연결 관계를 표현한다.

그래프는 다음으로 표현된다.

정점(Vertex) : 데이터를 표현 (사물, 개념) 등
간선(Edge) : 정점들을 연결하는데 사용

그래프는 이게 전부지만, 활용 분야가 워낙 많아서 내용은 굉장히 광범위하다.

그래프의 예시

예시) 소셜 네트워크 관계도

이 정보만 가지고도 여러 분석을 할 수 있다.
내가 그래프에서 0번 사람에 해당된다면, 내 친구는 1번과 3번인데 2번과 4번은 나를 직접은 모르지만 친구의 친구인 것은 알 수 있다.
나랑 3촌 관계 이내의 사람 => 엣지를 3번 이내로 타고 가서 나오는 사람들

가중치 그래프

ex) 지하철 노선도

각 역사이의 물리적 거리 or 걸리는 시간을 가중치로 표현
이 정보를 사용하여 간선의 가중치를 잘 조합해서 최단거리를 뽑아낼 수 있다.

방향 그래프

0에서 1로가는 간선과 1에서 0으로 가는 간선은 별도로 보아야 한다. 예시)

일반 통행이 포함된 도로망
두 사람 사이의 호감도

2. 그래프(Graph)의 구현 3가지

인스턴스 생성

LinkedList의 Node처럼 인스턴스를 생성하기
Vetex를 하나 하나씩 다 생성해준다.
edge를 하나씩 연결해준다.

가장 직관적인 방법은 이렇게 인스턴스를 생성하는 것이다.

class Vetex
{
	public List<Vertex> edges = new List<Vertex>();
}

void CreateGraph()
{
	List<Vertex> v = new List<Vertex>(6)
	{
		new Vertex(),
		new Vertex(),
		new Vertex(),
		new Vertex(),
		new Vertex(),
		new Vertex(),
	};

	v[0].edges.Add(v[1]);
	v[0].edges.Add(v[3]);
	v[1].edges.Add(v[0]);
	v[1].edges.Add(v[2]);
	v[1].edges.Add(v[3]);
	v[3].edges.Add(v[4]);
	v[5].edges.Add(v[4]);
}

이 방법에서 고려해볼 점
이렇게 인스턴스를 생성하는 부분이 안되는 것은 아니지만, 매번마다 new를 통해 정점을 만들어야 한다는 단점이 있습니다. 그리고 사실 그래프에서 정점의 개념은 추상적인 개념일 수도 있습니다. 당장에 정보가 없더라도 어떻게든 조합해서 만들 수 있는 정보인데, new를 통해 정점을 생성하면 낭비라는 생각이 들 수도 있습니다.

그래서 다음과 같이 인접 행렬 및 인접 리스트를 사용하는 방법이 있습니다.

인접행렬 사용

무방향 그래프에서 인접행렬을 사용하면 대칭의 형태가 나온다.
필요없는 정보까지 포함하는 경우가 있어서 메모리가 더 낭비된다.
시간적으로 효율적이다.
모든 값을 표현할 수 있을 크기로 2차원 배열을 만든다.
정점이 6개라면 6x6 배열을 만든다. 그리고 모든 경우의 수를 다 채워넣는다.
단점은 메모리 소모가 심할 수도 있다. 노드가 100개 있다면 100x100 즉, 10000개 짜리 정수를 저장하고 있어야 한다.
장점은 빠른 접근이 가능하다.
정점1에서 정점3으로 가는 길이 있는지 궁금하다면 그냥 좌표를 1,3에 해당하는 부분을 체크하면 된다.

int[,] adjacent2 = new int[6, 6]
{
	{ 0, 1, 0, 1, 0, 0 },
	{ 1, 0, 1, 1, 0, 0 },
	{ 0, 0, 0, 0, 0, 0 },
	{ 0, 0, 0, 0, 1, 0 },
	{ 0, 0, 0, 0, 0, 0 },
	{ 0, 0, 0, 0, 1, 0 },
};

가중치가 추가된 인접행렬

2차원 배열을 사용하면 인접리스트와는 다르게 한 번에 구현할 수 있다.

연결이 안되어 있는 것은 -1. (가중치에서는 사용안하는 음수값으로 끊긴 것을 표현)
연결된 곳은 가중치로 표현

int[,] adjacent2 = new int[6, 6]
{
	{ -1, 15, -1, 35, -1, -1 },
	{ 15, -1, 5, 10, -1, -1 },
	{ -1, -1, -1, -1, -1, -1 },
	{ -1, -1, -1, -1, 5, -1 },
	{ -1, -1, -1, -1, -1, -1 },
	{ -1, -1, -1, -1, 5, -1 },
};

인접 리스트 사용

리스트를 이용하는 방법은 0번에서 5번 노드 까지 일종의 태그를 줘서 몇 번째 정점인지 생각을 해보는 것이다. 정점을 객체가 아닌 정수로 생각해보는 것임.

각 정점마다 연결된 노드를 리스트로 표현한다.
각 정점의 개수마다 리스트가 존재한다.

메모리는 아낄 수 있지만, 접근 속도에서 손해를 본다. (간선이 적고 정점이 많은 경우 이점이 있다.)

1번 정점에서 3번 정점이 연결되어 있냐에 대한 질문이 들어온다면 빠르게 알 방법은 없다.
- 존재하는 방법은 2번째 리스트(1번째 정점과 이어진 정점정보를 가진 리스트)로 가서 3이 있는지 일일이 체크하는 방법밖에 없다.
- 즉, 임의 접근은 안되고 순회하면서 하나씩 체크해보아야 한다.

읽는 방법 : adjacent[from] -> 연결된 목록

List<int>[] adjacent = new List<int>[6]
{
	new List<int> { 1, 3 },
	new List<int> { 0, 2 , 3 },
	new List<int> {  },
	new List<int> { 4 },
	new List<int> {  },
	new List<int> { 4 },
};

방향성이 있는 것과 동시에 가중치도 있는 그래프를 표현해보자.

추가 정보가 필요하다면 추가 정보를 세트로 넣을 수 있도록 튜플을 이용하거나 매핑하는 클래스를 만들어서 넣어주면 된다.

class Edge
{
	public Edge(int v, int w) { vertex = v; weight = w;}
	public int vertex;
	public int weight;
}

List<Edge>[] adjacent = new List<Edge>[6]
{
	new List<Edge> { new Edge(1, 15), new Edge(3, 35) },
	new List<Edge> { new Edge(0, 15), new Edge(2, 5), new Edge(3, 10) },
	new List<Edge> {  },
	new List<Edge> { new Edge(4, 5) },
	new List<Edge> {  },
	new List<Edge> { new Edge(4, 5) },
};

3 그래프는 제공되는 클래스가 따로 없다.

그 이유는 앞의 것들만 봐도 경우에 따라서 구현이 달라지는 것을 볼 수 있다. 정점이 많은경우, 간선이 많은 경우에 따라서 배열 또는 리스트로 구현할 때 어느쪽이 효율이 더 좋은지가 나뉠 수도 있고, 양방향인지 아닌지, 가중치가 있는지 없는지에 따라 또 다르다. 그래서 우리가 한땀 한땀 구현해야하는 부분이다.

DFS 구현

1. 인접행렬의 DFS 구현

#include <iostream>
#include <stack>

#define NODE_COUNT 6

using namespace std;

// 재귀함수를 사용한 DFS
void dfs_recursion(int adj[][NODE_COUNT], int now, bool visited[])
{
	printf("%d\n", now);
	visited[now] = true;

	for (int next = 0; next < NODE_COUNT; next++)
	{
		if (adj[now][next] == 0)
			continue;
		if (visited[next]) // 다음에 방문할 곳이 이미 방문했던 곳이라면 continue.
			continue;
		dfs_recursion(adj, next, visited);
	}
}

// stack을 사용한 DFS
void dfs_stack(int adj[][NODE_COUNT], int now, bool visited[])
{
	stack<int> stk;
	stk.push(now);
	visited[now] = true;
	
	cout << stk.top() << endl;

	while (!stk.empty())
	{
		int top = stk.top();
		bool pop_flag = true;

		for (int next = 0; next < NODE_COUNT; next++)
		{
			if (adj[top][next] == 0)
				continue;
			if (visited[next])
				continue;
			
			stk.push(next);
			cout << stk.top() << endl;
			visited[next] = true;
			pop_flag = false;

			break;
		}

		// 반복문을 다 돌았다면, 기준노드와 관련된 곳을 모두 탐색했다는 뜻이므로 pop을 해준다.
		if (pop_flag)
		{
			stk.pop();
		}
	}
}

int main()
{
	int adj[NODE_COUNT][NODE_COUNT] =
	{
		{ 0, 1, 0, 1, 0, 0 },
		{ 1, 0, 1, 1, 0, 0 },
		{ 0, 1, 0, 0, 0, 0 },
		{ 1, 1, 0, 0, 1, 0 },
		{ 0, 0, 0, 1, 0, 1 },
		{ 0, 0, 0, 0, 1, 0 },
	};

	bool visited[NODE_COUNT] = { false, };
	int start_node = 0;

	//dfs_recursion(adj, start_node, visited);
	dfs_stack(adj, start_node, visited);

	return 0;
}

2. 인접리스트의 DFS 구현

#include <iostream>
#include <vector>
#define VERTICES_COUNT 6

using namespace std;

vector<int> adjacent[VERTICES_COUNT]
{
	vector<int> { 1, 3 },
	vector<int> { 0, 2, 3 },
	vector<int> {  },
	vector<int> { 4 },
	vector<int> {  },
	vector<int> { 4 },
};

bool visited[VERTICES_COUNT] = { false, };

void dfs(int now)
{
	cout << now << endl;
	vector<int> vertex = adjacent[now];
	visited[now] = true;

	for (int next = 0; next < VERTICES_COUNT; next++)
	{
		if (visited[next])
			continue;
		dfs(next);
	}
}


int main()
{
	dfs(0);

	return 0;
}

참고자료

C#과 유니티로 만드는 MMORPG 게임 개발 시리즈 Part2: 자료구조와 알고리즘
인정행렬에서 DFS 구현

Junsu Park