그래프(너비우선, 깊이우선)

연결된 목록을 좀 더 융통성 있게 만들면 트리가 된다.

(트리 역시 노드 기반 자료구조이고 연결된 목록과는 달리 각 노드가 여러 개의 자식 노드들이 있기때문에)

(오직 하나의 자식만들 가진 트리가 연결된 목록이다)

트리를좀 더 융통성있게 만들면? 그것은 바로 그래프가 된다.

트리의 각 노드는 자시의 아래 수준의 노드만을 가리킨다.

이런 제한을 없애서 어떤 노드도 가리킬 수 있도록 하면? 그래프다.

 

그럼 역으로 ..

그래프에 수준(높이)라는 제한을 적용하면 트리가 되고, 트리에 하나의 자식 노드라는 제한을 적용하면 연결된 목록이 된다.

 

그래프의 종류

양방향 그래프

단방향 그래프

가중 그래프

타일맵(사이사이가 서로 양방향으로 연결..)

 

그래프의 구현방법

1. 2차원 배열

  : 2차원 배열로 구현된 그래프의 호(선)들은 오직 이론만 존재.

  : 그냥 상 (y-1) 하(y+1)...이런식으로 하면 되니까..

2. 인접성 참조표

  : 2차원 배열을 사용함.

  : 2차원 배열에 노드들을 담는것이 아니라 노드들 사이의 관계에 대한 정보를 담는다.

  : 항상 정방형이며 양 축의 크기는 노드들의 개수이다.

 

	A	B	C
A		20	100
B	20
C	100

위의표에는 총 3개의 노드들이 있으므로 인접성 참조표의 크기는 3x3이다.

이표를 사용하는 방법은 A로부터 B로 가는 비용을 알고 싶다면 x축에서A y축에서 B를 찾는다. 교차하는 그 수가 비용이다.

하지만 이건 공간의 낭비가 심하다.

또 다른 문제는 이런 방법이 단방향 그래프에만 유용하다는 점.

 

3. 방향 참조표

  : 이역시 2차원 배열에 인접성 정보를 저장하는데 인접성 참조표보다는 공간을 적게 차지한다.

  : 한 노드에서 이동할 수 있는 방향들이 미리 결정되어 있다고 가정

  : 예를 들어서 한 노드의 출구들이 동,서,남,북 네방향에만 존재한다고 하자.

    방향이 4개 일떄 방향 참조표의 크기는 N * 4이다. 여기서 N은 노드들의 개수

 

	북	동	남	서
0		1	2
1				0
2	0	3
3		4	5	2
4				3
5	3

: 0의 동쪽에 1이 있고 남쪽에 2가 있다. 이렇게 보면됨.

이 예에서 보듯이 이 방법은 던전 비슷한맵, 즉 방들이 흩어져 있고 그 사이를 길고 복잡한 통로가 연결하는 형태의 맵을 저장하기에 매우 적합

: 단 방향 그래프에도 응용할 수 있다.

 

4. 연결된 그래프

가장 일반적인 방식으로 연결된 트리 같은 노드 연결 방식을 사용하는것

4-1) 양방향 그래프

두개의 개별적인 자료구조, 즉 그래프 노드와 그래프 호를 이용해서 간단하게 구현할 수 있다.

그래프 노드들의 배열(또는 연결된 목록)과 그래프 호들의 배열(또는 연결목록)로 구성된다.

그래프 노드는 특정 노드의 자료를 저장하는 역활

그래프 호는 두개의 포인터를 가진다(가중치가 있을 경우 가중치 변수도 갖는다)

4개의 노드와 3개의 호들이 있다면

 

(양방향의 화살표가 없으나 확실히 양방향 연결이다)

내부적으로는 그래프의 자료를 담은 노드 4개짜리 배열과 노드들 사이의 연결 정보를 의미하는 호 3개짜리 배열로 구성된다.

노드들만으로는 연결에 대한 정보를 알 수 없으며 따라서 한 노드가 어떤 노드를 가리키는지 알아내려면

모두 검색해야한다.  느리다.

이러한 문제를 해결하기 위해서 각 노드마다 그 노드에 관련된 호들의 연결된 목록을 집어넣는다면?

 

(호에서 노드로 가는 선이 빠졌으나 실제로 있게되면 엄청 복잡해진다.)

그냥 위의 2가지 방법은 절대로 사용하지 말자. 매우 복잡해진다.

 

5. 단방향 그래프

그래프 중 가장 일반적인 형태로 매우 유연하며 양방향 방법보다 빠르다.

자료가 노드 클래스의 배열(또는 연결 목록)에 저장되는 점은 동일한다.

틀린점은 호는 클래스? 배열?이 따로 존재하는것이 아니다.

이 방법에서 호는 본질적으로 한 노드에 대한 포인터이며(여기에 추가적으로 가중치가 부여될 수 있다)(위에서는 호 따로 노드 따로 따로따로다)

그래프의 각 노드는 그러한 호들의 연결목록을 가진다.

(각 노드는 다른 노드를 가리키는 호들의 연결목록을 가진다)

 

 

그래프의 운행

그래프를 운행하는 방법은 크게 두 가지로 나뉜다.

첫번째는 깊이 우선탐색(트리의 운행 알고리즘과 비슷하다.)

두번째는 너비 우선탐색(게임프로그래밍에선 이것이 더 유용하다)

트리와 그래프 운행의 주된 차이는 트리의 경우 항상 루트이지만 그래프는 어느 노드에서도 시작한다.

 

1. 깊이 우선 탐색

깊이 우선 탐색은 전위 운행과 거의 비슷하다.

이미 처리된 적이 있는지 식별할 수 있는 수단이 필요함.

의사코드는(전위 운행과 다른부분은 굵은 글씨)

DepthFirst(Node)

Process(Node) //노드 처리

Mark(Node)

For Every Child of Node

IF NotMarkded(Child)

DepthFirst(Child)

End IF

End For

End Function

 

실제 응용할때는 항상 스택을 이용해서 깊이 우선 탐색을 구현한다.(위에는 재귀임)

스택에서는

각 노드를 처리할때마다 노드를 스택에 넣는다.

다른 노드로의 연결이 없는 노드를 만나면 스택에서 이전 노드를 뽑고 그 노드에 아직 처리되지 않은 다른 노드들이 있는지 점검해서 남은 노드들을 처리한다.

 

스택으로 활용한 의사코드를 표현하자면

DepthFirst(Node)

Process(Node)

Mark(Node)

Push(Node)

While(Stack Empty!)

Temp=Stack.POP

Process(Temp)

For Every Child of Node

IF NotMarked(Child)

Mark(Child)

Push(Child)

End IF

End For

End While

End Function

2. 너비우선 탐색

깊이 우선 탐색과는 다르게 너비 우선은 넓게 펼쳐나간다는 느낌을 갖는다.

현재 노드로부터 직접 이동할 수 있는 가장 가까운 노드들을 먼저 훑고 그 다음으로 한 단계 건너뛴 곳의 노드들을 훑고 그 다음으로는 한 단계 더 먼 노드들을 훑는 식이다.

직접 연결된 노드들이 가장 먼저 처리되며 그 다음 그 노드들에 연결된 노드들이 차례로 처리된다.

(시작노드와 가장 가까운 노드들이 먼저 처리되고 먼 노드일수록 나중에 처리 된다.)

너비우선은 대기열이 필요하다.(큐~)

너비 우선 탐색 알고리즘의 의사코드는

BreadthFirst(Node)
    Queue.Enqueue(Node)

Mark(Node)

while(Queue.NotEmpty)

Process(Queue.Front)

For Each Child of Queue.Front

If Not Marked(Child)

Queue.Enqueue(child)

Mark(Child) //노드를 처리할때가 아니라 노드를 대기열에 넣을 때 노드에 표시를 한다. 노드가 대기열에 여러번 들어가는것을 막기위해) 

End If

End For

Queue.Dequeue()

End While

End Function

깊이 우선 탐색보다는 너비 우선 탐색은 게임 프로그래밍에서 매우 중요한 알고리즘이다.

두 알고리즘의 공통점은 주어진 시작 지점에서 도달할 수 있는 모든 노드들을 처리한다는 것이다.

 

---

 

GraphArc (그래프 호 클래스)

 

//GraphArc 클래스내에 아직 미선언된 GraphNode에 대한 전방선언
template  class GraphNode;

template
class GraphArc
{
public:
	GraphNode* m_node; //호가 가리키는 그래프 노드를 저장한다
	Arctype m_weight; //호가 가지는 가중치
};

 

GraphNode(그래프 노드 클래스)

 

template
class GraphNode
{
public:
	typedef GraphArc Arc;
	typedef GraphNode Node;

	Nodetype m_data; //노드에 저장될 데이터
	DLinkedList m_arcList; //하나의 연결된 목록을 포함하는데..다른 노드가 아니라 호(Arc)을 담는다.
	bool m_marked; //표시여부

	GraphNode()
	{
		m_marked = false;
	}
	~GraphNode()
	{}

	//현재 노드에 호를 하나 추가한다. 호가 가리키는 노드와 가중치를 매개변수로 받는다
	void AddArc(Node* p_node, Arctype p_weight)
	{
		Arc a;
		a.m_node = p_node;
		a.m_weight = p_weight;
		m_arcList.Append(a);
	}

	Arc* GetArc(Node* p_node)
	{
		DListIterator itr = m_arcList.GetIterator();
		for (itr.Start(); itr.Valid(); itr.Forth())
		{
			if (itr.Item().m_node == p_node) //왜 여기서 인텔리센스가 안될까..
			{
				return &(itr.Item());
			}
		}
		return 0;
	}

	void RemoveArc()
	{
		DListIterator itr = m_arcList.GetIterator();
		for (itr.Start(); itr.Valid(); itr.Forth())
		{
			if (itr.Item().m_node == p_node)
			{
				m_arcList.Remove(itr);
			}
		}
	}
};

 

Graph(그래프 클래스)

그래프 클래스를 구현하는 방법은 여러가지이다. 노드 클래스에서 이미 봤듯이 호들은 연결된 목록에 저장된다.

각 노드별 m_arcList에 호들이 연결된 목록으로 저장된다.

그래프의 호들은 자주 변하기 마련이므로 항목들의 추가, 제거가 쉬운 연결된 목록..

 

노드는 그러나 좀 다르다. 그래프에서는 노드의 삽입 제거는 그다지 빈번하게 일어나지 않는다.

연결된 목록대신에 배열을 사용한다.

 

//실제의 그래프 클래스
//여기서 모든 노드와 호를 관리 한다. 그래프 관련된 일은 다함
template
class Graph
{
public:
	typedef GraphArc Arc;
	typedef GraphNode Node;

	//변수는 2개다 Node포인터들의 배열, 노드들의 개수
	Array m_nodes;
	int m_count;

	Graph(int p_size) : m_nodes(p_size)
	{
		int i;
		for (i = 0; i < p_size; i++)
		{
			m_nodes[i] = nullptr;
		}
		m_count = 0;
	}

	~Graph()
	{
		int index;
		for (index = 0; index < m_nodes.Size(); index++)
		{
			if (m_nodes[index] != nullptr)
			{
				delete m_nodes[index];
			}
		}
	}

	//이 그래프는 배열을 쓰기 때문에 색인을 통해서 특정한 노드에 직접 접근할 수 있다.
	//이런 과정때문에 삽입, 제거가 매우 간단하다.
	bool AddNode(Nodetype p_data, int p_index)
	{
		if (m_nodes[p_index] != nullptr)
		{
			return false;
		}

		m_nodes[p_index] = new Node;
		m_nodes[p_index]->m_data = p_data;
		m_nodes[p_index]->m_marked = false;
		m_count++;
		return true;
	}

	//그래프에서 노드 제거는 그냥 노드하나를 지우는걸로 끝나지 않는다.(트리나 연결목록도 그렇지만..)
	//단방향이기 때문에 반드시 제거된 노드를 가르키는 호(Arc)가 있는데 이걸 해결해야한다.(연결된 목록하고 트리도..)
	//그래서 그 노드를 가리키는 모든 호들을 찾아서 삭제해야한다.

	void RemoveNode(int p_index)
	{
		if (m_nodes[p_index] == nullptr)
		{
			return;
		}

		int node;
		Arc* arc;

		//2중으로 내포된 for루프다. **모든 노드들의 모든 호들을 검색하니까**
		//그래프에서 모든 노드들은 그래프의 임의의 노드들을 가리킬 수 있으며
		//이는 최악의 경우 모든 노드들이 다른 모든 노드들에 대한 포인터를 가질 수 있다는 뜻..
		for (node = 0; node < m_nodes.Size(); node++)
		{
			if (m_nodes[p_index] != nullptr)
			{
				arc = m_nodes[p_index]->GetArc(m_nodes[p_index]);
				if (arc != nullptr)
				{
					RemoveArc(node, p_index);
				}
			}
		}
		delete m_nodes[p_index];
		m_nodes[p_index] = nullptr;
		m_count--;
	}

	bool AddArc(int p_from, int p_to, Arctype p_weight)
	{
		if (m_nodes[p_from] == nullptr || m_nodes[p_to] == nullptr)
		{
			return false;
		}
		if (m_nodes[p_from]->GetArc(m_nodes[p_to]) != nullptr)
		{
			return false;
		}
		m_nodes[p_from]->AddArc(m_nodes[p_to], p_weight);
		return true;
	}

	void RemoveArc(int p_from, int p_to)
	{
		if (m_nodes[p_from] == nullptr || m_nodes[p_to] == nullptr)
		{
			return;
		}

		//RemoveArc함수는 GraphNode에 있으며 해당 노드를 매개변수를 넘기면
		//노드안에 있는 연결목록에서 해당 노드를 가리키는 것을 찾아서 삭제함
		m_nodes[p_from]->RemoveArc(m_nodes[p_to]);
	}

	//호를 가리키는 포인터를 반환
	Arc* GetArc(int p_from, int p_to)
	{
		if (m_nodes[p_from] == nullptr || m_nodes[p_to] == nullptr)
		{
			return 0;
		}
		return m_nodes[p_from]->GetArc(m_nodes[p_to]);
	}


	//모든 표시를 false로 해둔다. 운행 알고리즘 시작전에 반드시 실행
	void ClearMarks()
	{
		int index;
		for (index = 0; index < m_nodes.Size(); index++)
		{
			if (m_nodes[index] != nullptr)
			{
				m_nodes[index]->m_marked = false;
			}
		}
	}
};

	void DepthFirst(Node* p_node)//void(*p_process)(Node*))
	{
		if (p_node == nullptr)
		{
			return;
		}

		p_process(p_node);
		p_node->m_marked = true;

		//반복자를 하나 만들고 현재 노드의 모든 호들을 훑으면서 표시하지 않은
		//노드를 가리키는 호가 있으면 그 노드에 대해서 DepthFirst 함수를 재귀적으로 호출
		DListIteratoritr = p_node->m_arcList.GetIterator();

		for (itr.Start(); itr.Valid(); itr.Forth())
		{
			if (itr.Item().m_node->m_marked == false)
			{
				DepthFirst(itr.Item().m_node);
			}
		}
	}

	void p_process(Node* node)
	{
		cout << node->m_data << endl;
	}
	

위에 깊이우선 탐색함수는 매개변수를 시작노드를 받는다.

	//너비우선 탐색
	void BreadthFirst(Node* p_node)
	{
		if (p_node == nullptr)
		{
			return;
		}

		LQueue queue; //너비우선 탐색은 대기열로 구현한다.
		DListIterator itr;

		queue.Enqueue(p_node);
		p_node->m_marked = true;

		while (queue.m_count != 0)
		{
			p_process(queue.Front()); //첫번째 노드 처리하고 또는 대기열에서 처음노드를 뽑아서 처리하고
			itr = queue.Front()->m_arcList.GetIterator(); //뽑힌 해당노드에서 자식을 탐색하자
			for (itr.Start(); itr.Valid(); itr.Forth())
			{
				if (itr.Item().m_node->m_marked == false) //해당 노드의 자식 노드들 중 표시가 안된것들을
				{
					itr.Item().m_node->m_marked = true; //표시해두고
					queue.Enqueue(itr.Item().m_node);  //대기열에 넣는다
				}
			}
			queue.Dequeue(); //해당 자식들 다봤으면 뽑힌 노드 지워버리고
		}
	}