[자료구조] 그래프

그래프는 관계에 특화된 자료 구조로 정점(Vertex)과 간선(Edge)으로 구선된다.

 

정점 : 고유하게 식별되는 객체

간선 : 정점간의 관계

 

 

종류

그래프는 간선이 방향성을 가지는 방향 그래프와 무방향 그래프로 구분할 수 있고 간선이 단순 연결 이상의 정보를 가지는 가중치 그래프등 여러가지 종류가 있다.

 

여러가지 그래프

 

용어 정리

 

인접(Adjacent) : 간선으로 연결된 정점끼리를 부르는 말

부속(Incident) : 정점에 연결된 간선

차수(Degree) : 정점에 부속된 간선의 수

진입 차수(In - Degree) : 정점으로 들어오는 방향

진출 차수(Out - Degree) : 정점으로 나가는 방향

 

경로(Path) : 한 정점에서 다른 정점까지 간선으로 연결된 정점을 순서대로 나열한 리스트

경로 길이(Path length) : 경로를 구성하는 간선의 수

단순 경로(Simple Path) : 모두 다른 정점으로 구성된 경로

사이클(Cycle) : 단순 경로 중 경로의 시작과 마지막 정점이 같은 경로

연결(Connected) : 정점끼리 경로가 있을 때 하는 말

 

그래프의 표현 방법

 

그래프의 표현 방법에는 인접행렬과 인접리스트가 있다.

 

인접 행렬

 

정점이 N개 있을 경우 N * N 크기의 2차원 배열로 그래프를 표현할 수 있다.

여기서 배열의 원소는 간선의 가중치를 나타낸다.

예시 )  정점 [ i ][ j ] 는 정점 i에서 정점j로 가는 간선을 나타낸다.

 

배열의 사용하기 때문에 그래프에 *간선이 적으면 그만큼 메모리가 낭비된다.

 

*희소 그래프(Sparse Graph) : 간선이 적은 그래프

*밀집 그래프(Dense Graph) : 간선이 많은 그래프

 

// 정점이 7개라면 7 * 7의 2차원 배열을 정의해준다.
int graph[7][7];
 
// 무방향 그래프이므로 서로 연결해준다.
graph[0][1] = 1; // 0 -> 1의 방향과 1의 가중치를 가진 간선
graph[1][0] = 1; // 1 -> 0의 방향과 1의 가중치를 가진 간선
 
graph[1][2] = 2; // 1 -> 2의 방향과 2의 가중치를 가진 간선
graph[2][1] = 2; // 2 -> 1의 방향과 2의 가중치를 가진 간선

graph[1][3] = 2; // 1 -> 3의 방향과 2의 가중치를 가진 간선
graph[3][1] = 2; // 3 -> 1의 방향과 2의 가중치를 가진 간선
 
// 이하 설명 생략
graph[2][5] = 6;
graph[5][2] = 6;
graph[2][6] = 3;
graph[6][2] = 3;
 
graph[3][4] = 1;
graph[4][3] = 1;
graph[3][5] = 4;
graph[5][3] = 4;

 

인접 리스트

인접 리스트는 각 정점에 연결된 정점의 ID만 저장하는 방식으로 그래프를 표현한다.

 

//그래프를 저장하기 위한 벡터
//정점을 int로 관리하고 정점이 7개기에 아래와 같이 정의함
std::vector<int> graph[7];
 
// 0번 정점에서 진출하는 간선을 모두 저장한다.
graph[0].push_back(1);
 
// 1번 정점에서 진출하는 간선을 모두 저장한다.
graph[1].push_back(0);
graph[1].push_back(2);
graph[1].push_back(3);
 
// 2번 정점에서 진출하는 간선을 모두 저장한다.
graph[2].push_back(1);
graph[2].push_back(5);
graph[2].push_back(6);
 
// 이하 설명 생략
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
 
graph[4].push_back(3);
 
graph[5].push_back(2);
graph[5].push_back(3);
 
graph[6].push_back(2);

 

위와 같이 그래프를 만들었다면 최종적으로 아래와 같이 벡터에 저장된다.

 

[0] : { 1 }
[1] : { 0, 2, 3 }
[2] : { 1, 5, 6 }
[3] : { 1, 4, 5 }
[4] : { 3 }
[5] : { 2, 3 }
[6] : { 2 }

 

순회

순회는 한 정점에서 시작해 그래프에 있는 모든 정점을 한 번씩 방문하는 것을 말한다.

 

순회 방식에는 너비 우선 탐색(Breadth First Search)과 깊이 우선 탐색(Depth First Search)이 있다.

 

너비 우선 탐색

너비 우선 탐색은 시작정덤에 인접한 정점을 차례대로 모두 방문하고 나서 방문한 정점을 시작으로 다시 인접한 정점을 차례로 방문하는 방식으로 탐색한다.

큐(queue)를 사용함.

 

너비 우선 탐색을 위의 그래프로 예시를 든다면

알아보기 쉽게 낮은 숫자를 우선 탐색한다고 친다.

1에서 시작한다고 하면 1에서 먼저 붙어있는 0, 2, 3 을 탐색하고 다음 2와 붙어있는 5, 6 다음 3과 붙어있는 4를 탐색한다.

그래서 탐색 순서는 1 -> 0 -> 2 -> 3 -> 5 -> 6 -> 4 가 된다.

 

깊이 우선 탐색

깊이 우선 탐색은 시작 정점의 한 방향으로 갈 수 있는 경로가 없을때까지 탐색하다 더이상 갈 곳이 없다면 마지막에 만난 갈림길 간선이 있는 정점으로 돌아와 다른 방향으로 탐색하는 방식이다.

스택(stack)을 사용함.

 

알아보기 쉽게 낮은 숫자를 우선 탐색한다고 친다.

1에서 시작한다고 하면 1에서 가장 낮은 0을 먼저 탐색하고 길이 막혔으니 다시 1로 돌아와 다름 순서인 2로 가게 된다.

그리고 2에는 5, 6 이 연결되어 있어 우선 순위인 5로 가고 5에선 연결된 3으로 그리고 3에선 4로 가면 더 이상 갈 수가 없게 되는데 여기서 가장 마지막 갈림길인 2로 돌아와 6으로 가게 된다.

그래서 탐색 순서는 1 -> 0 -> 2 -> 5 -> 3 -> 4 -> 6 이 된다.