[자료구조] 그래프

그래프는 데이터가 어떻게 연결되는지 쉽게 이해시키므로 관계에 특화된 자료구조다.

한 사람은 한 노드로, 사람 간 관계는 각 선으로 표현한다. 그래프 용어로 각 노드를 정점이라 부르고, 각 선은 간선이라 한다. 간선으로 연결된 정점들은 서로 인접한다고 말한다. 그래프를 구현하는 방법은 많지만 가장 간단한 방법 중 하나는 해시 테이블을 사용하는 것이다. 해시 테이블의 모든 키 값은 한 단계로 찾을 수 있으므로 그래프를 쓰면 앨리스의 친구를 O(1)에 찾을 수 있다.

 

SNS의 팔로우를 본다면 관계가 상호적이지 않다. 앨리스는 밥을 팔로우할 수 있지만, 밥이 반드시 앨리스를 팔로우하지는 않는다.

화살표의 방향은 관계의 방향을 나타낸다. 위 둘 예제는 서로 비슷하지만 각각 관계의 본질이 다르다. 관계의 방향성을 표현할 때는 화살표를 사용하고 방향 그래프라 부르며 관계가 상호적일 경우에는 단순 선을 사용하고 무방향 그래프라 부른다. 간단한 해시 테이블로 그래프를 표현할 수 있지만, 보다 강력한 객체 지향 구현도 가능하다.

 

C++로 간단히 구현하면 아래와 같다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

class CPerson
{
public:
	CPerson(string _name) : name(_name) {}

	void add_firend(CPerson* person)
	{
		friends.push_back(person);
	}

	string name;
	vector<CPerson*> friends;
};

int main()
{
	CPerson* mary = new CPerson("Mary");
	CPerson* peter = new CPerson("Peter");
	mary->add_firend(peter);
	peter->add_firend(mary);
	return 0;
}

---

너비 우선 탐색

그래프를 순회하는 전형적인 방법은 두 가지다. 너비 우선 탐색과 깊이 우선 탐색이다. 둘은 상당히 유사하고 대부분은 똑같이 잘 작동한다. 너비 우선 탐색 알고리즘은 다음으로 처리할 정점을 추적하기 위해 큐를 사용한다. 최초의 큐는 시작점만 포함한다. (Alice로부터 시작한다고 하자)

 

첫 큐는 [Alice]로 표현할 수 있을 것이다.

 

이어서 큐로부터 앨리스를 삭제해서 앨리스 정점을 처리한다. 앨리스 정점에는 "방문했음"이라고 표시하고, 이 정점을 현재의 정점으로 저장한다. 이어 다음의 세 단계를 따른다.

1. 현재 정점과 인접한 각 정점을 방문한다. 이전에 방문한 적 없는 정점이면 방문했다고 표시하고 큐에 추가한다. (이 정점은 아직 현재 정점이 아니다.)
2. 현재 정점에 인접한 정점을 모두 방문했으면 큐로부터 다음 정점을 제거해서 현재 정점으로 만든다.
3. 현재 정점에 인접한 정점을 모두 방문했고 큐에  더 이상 정점이 없으면 알고리즘을 종료한다.

실제로 동작을 확인해 보자.

 

먼저 앨리스를 현재 정점으로 만들면서 시작한다. 우선 Alice가 정점임을 표시하고 방문했다는 의미로 체크 부호를 표시한다. 이어 방문하지 않은 인접 정점인 밥을 방문함으로써 알고리즘을 계속 수행한다.

 

 밥의 이름에도 체크 부호를 추가하고 큐에도 추가한다. 이제 큐는 [Bob]이다. 아직 밥은 현재 정점은 아니다. 중요한 것은 앨리스가 현재 정점이더라도 여전히 밥을 방문할 수 있다.

 

다음으로 현재 정점인 앨리스의 인접 정점 중 방문하지 않은 정점이 있는지 확인한다. 캔디가 있으므로 캔디를 방문한다. 남은 드렉과 일레인도 방문한다.

이제 큐는 [Bob, Candy, Derek, Elaine]이다.

 

현재 정점인 앨리스의 인접 정점을 모두 방문했으므로 큐에서 정점을 pop 해서 그 정점을 현재 정점으로 만드는 다음 알고리즘 규칙으로 넘어간다. 큐는 앞에서만 데이터를 제거할 수 있고 여기서는 밥이다. 밥의 인접 정점은 프레드 하나 있으므로 프레드를 방문했다고 표시하고 큐에 추가한다.

 

이제 큐는 [Candy, Derek, Elaine, Fred] 다.

 

다음은 캔디를 pop 해서 정점으로 만든다. 하지만 캐디에는 방문하지 않은 인접 정점이 없다. 따라서 그다음 항목인 드렉을 pop 한다.

 

이제 큐는 [Elaine, Fred] 다.

 

드렉에는 지나가 인접 정점으로 존재하므로 체크하고 큐에 추가한다. 

 

이제 큐는 [Elaine, Fred, Gina] 다.

 

다음으로 일레인을 pop 하여 정점으로 만들지만 일레인에는 인접 정점이 존재하지 않는다. 다음 프레드를 pop 한다.

 

이제 큐는 [Gina] 다.

 

프레드에 인접한 헬렌을 큐에 추가하면 큐는 [Gina, Helen]이 된다.

다음으로 Gina를 pop 하여 인접한 이레나를 정점으로 큐에 추가한다. 이제 큐는 [Helen, Irena] 다.

헬렌과 이레나는 둘 다 인접하는 정점이 없으므로 차례대로 pop 하면 끝나게 된다.

---

코드 구현

올바른 동작을 위해 탐색에서 어떤 사람을 방문했는지 기록하는 visited 속성도 CPerson 클래스에 추가하였다. 그래프 너비 우선 탐색은 다음과 같이 알고리즘의 단계를 두 종류로 나눠서 효율성을 계산할 수 있다.

• 큐에서 정점을 삭제해 현재 정점으로 지정한다.
• 각 현재 정점마다 그 정점의 인접 정점을 각각 방문한다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

class CPerson
{
public:
	CPerson(string _name) : name(_name), visited(false) {}

	void add_firend(CPerson* person)
	{
		friends.push_back(person);
	}

	void displayNetwork()
	{
		queue<CPerson*> reset;
		reset.push(this);
		queue<CPerson*> q;
		q.push(this);
		visited = true;

		while (!q.empty())
		{
			CPerson* p = q.front();
			q.pop();
			cout << "node name : " << p->name << endl;

			for (int i = 0; i < (int)p->friends.size(); i++)
			{
				if (!p->friends[i]->visited)
				{
					reset.push(p->friends[i]);
					q.push(p->friends[i]);
					p->friends[i]->visited = true;
				}
			}
		}

		while (!reset.empty())
		{
			reset.front()->visited = false;
		}
	}

	string name;
	bool visited;
	vector<CPerson*> friends;
};

int main()
{
	CPerson* alice = new CPerson("Alice");
	CPerson* bob = new CPerson("Bob");
	CPerson* candy = new CPerson("Candy");
	CPerson* derek = new CPerson("Derek");
	CPerson* elaine = new CPerson("Elaine");
	CPerson* fred = new CPerson("Fred");
	CPerson* helen = new CPerson("Helen");
	CPerson* gina = new CPerson("Gina");
	CPerson* irena = new CPerson("Irena");

	alice->add_firend(bob);
	alice->add_firend(candy);
	alice->add_firend(derek);
	alice->add_firend(elaine);

	bob->add_firend(fred);
	fred->add_firend(helen);

	derek->add_firend(gina);
	gina->add_firend(irena);

	alice->displayNetwork();
	return 0;
}