그래프 알고리즘

  동적 프로그래밍 

그래프 기본 개념

현상이나 사물을 정점과 간선으로 표현하는 것을 말한다.

• 정점(Vertex) 대상이나 개체
• 간선(Edge) 대상이나 개체 간의 관계

 

그래프는 간선이 상호 통행이 가능한지, 일방통행만 가능한지에 따라 유향 그래프와 무향 그래프로 나뉜다.

• 유향 그래프 정해진 방향으로만 이동이 가능한 그래프, 화살표로 간선을 표현한다.
• 무향 그래프 쌍방으로 이동이 가능한 그래프, 실선으로 간선을 표현한다.

 

쉽게 배우는 알고리즘 그래프 그림 9-1, 9-3

 

또, 각각의 정점이 가지는 관계의 정도를 간선에 가중치로 표현하기도 한다.

 

쉽게 배우는 알고리즘 그래프 그림 9-2, 9-4

 

인접 행렬을 이용한 그래프의 표현

각 행, 열을 순서대로 정점을 나타내고 각각의 간선은 해당하는 행, 열의 위치에 값을 할당하는 방식으로 그래프를 표현하여 이해하기 쉽고 간선의 존재 여부를 곧바로 파악할 수 있다.

 

가중치를 가지는 그래프의 경우 단순히 행렬에 적용하는 값을 가중치로 넣어 표현한다.

 

쉽게 배우는 알고리즘 그래프 그림 9-5, 9-8

 

※ 간선의 밀도가 아주 높은 그래프의 경우 인접 행렬 표현이 적합하다.

 

인접 리스트를 이용한 그래프의 표현

인접 리스트 표현법은 리스트를 정점의 길이만큼으로 만들고 각 정점이 연결된 정점을 노드로 연결하는 방식으로 행렬 표현 방식에 비해 공간의 낭비가 없다는 장점이 있다.

 

노드의 구성은 기본적으로 <정점 번호, 다음 노드의 포인터>로 구성되며 가중치를 가지는 그래프의 노드는 추가로 가중치를 넣어 표현한다.

 

쉽게 배우는 알고리즘 그래프 그림 9-10

 

※ 모든 가능한 정점 쌍에 비해 간선의 수가 적은 그래프의 경우 유용하게 사용할 수 있다.

 

너비 우선 탐색과 깊이 우선 탐색

그래프에서 모든 정점을 탐색하는 방법에는 레벨의 모든 노드를 방문하는 것을 우선하는 너비 우선 탐색(Breath First Search)과 루트에서부터 한 방향으로 리프 노드가 나올 때까지 진행하는 깊이 우선 탐색(Depth First Search)이 존재한다.

 

쉽게 배우는 알고리즘 그래프 그림 9-11

 

너비 우선 탐색 알고리즘

너비 우선 탐색은 먼저 방문한 노드를 먼저 처리하는 FIFO 방식이므로 Queue를 사용한다.

 

BFS 알고리즘

BFS(G, s)
{
	for each v ∈ V - {s}
	{
		visited[v] ← NO;
	}

	visited[s] ← YES;
	enqueue(Q, s);

	while (Q ≠ ∮)
	{
		u ← dequeue(Q);
		for each v ∈ L(u)
		{
			if (visited[v] = NO) then
			{
				visited[v] ← YES;
				enqueue(Q, v);
			}
		}
	}
}

 

깊이 우선 탐색 알고리즘

깊이 우선 탐색은 나중에 방문한 노드를 먼저 처리하는 LIFO 방식이므로 Stack을 사용한다.

 

DFS 알고리즘

DFS(G, s)
{
	for each v ∈ V - {s}
	{
		visited[v] ← NO;
	}

	for each v ∈ V - {s}
	{
		if (visited[v] = NO) then
		{
			aDFS(v);
		}
	}
}

aDFS(v)
{
	visited[s] ← YES;
	for each v ∈ L(u)
	{
		if (visited[v] = NO) then
		{
			aDFS(v);
		}
	}
}

 

https://github.com/NadanKim/Algorithm

GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘