그래프란?

• 그래프(Graph)

 

 

그래프(graph)는 정점(vertex)과 간선(edge)로 구성되어 있는 자료구조로, 원소들간의 연결 관계를 명확하게 나타내기 위해 사용된다.

 

 

그래프의 예시이다

 

 

 

 

각 원소들을 나타내는 동그라미 부분이 정점(vertex, 혹은 노드(node)라고도 부른다), 정점들을 이어 연결 여부를 나타내는 선분은 간선(edge)라고 부른다.

 

 

정점의 집합은 V={0, 1, 2, 3, 4, 5, 6}로 나타낼 수 있다.

 

 

간선의 집합은 양 끝의 정점 쌍으로 표시한다. $E=${($0, 1$), ($0, 2$), ($1, 3$), ($1, 4$), ($2, 5$), ($3, 6$), ($4, 6$)}이다.

 

 

 

---

 

• 그래프의 용어들

 

 

• 차수(degree): 어떤 정점과 이어진 간선의 개수

              ex) 0번 정점의 차수는 2이다.

 

• 인접하다(adjacent): 두 개의 정점이 하나의 간선으로 직접 연결되어 있다.

              ex) 0번 정점은 1번 정점과 인접하다.

 

• 사이클(cycle): 한 정점에서 출발해 다시 시작 정점으로 들어오는 경로

              예시는 아래에 있다.

 

 

---

 

 

그래프의 분류

 

 

 

 

• 방향성

 

 

 방향성이 있다는 말의 정의는 정점 A에서 정점 B로 간선을 통해 이동하는데 그 간선이 한 방향으로만 되어있음을 의미한다.  방향성이 있는 그래프를 유향 그래프라고 하고, 방향성이 없으면 무향 그래프라고 한다.

예를 들어 아래 그래프에서 1번 정점에서 3번 정점으로 가는 간선은 1에서 3으로의 방향성을 가지고 있다. 위 그래프의 경우는 모든 간선들이 단방향의 방향성을 가지고 있다(유향 그래프).

 

 

 

아까 위에서 언급한 사이클(cycle)이 이 유향 그래프에서 (1->3, 3->6, 6->4, 4->1)로 나타나고 있다.

 

 

 

---

 

 

• 가중치

 

 

 

  가중치가 있다는 것은 간선에 어떤 값, 예를 들면 특정 도시에서 다른 도시로 이동하는데 걸리는 시간이나 비용 등의 값이 정의되어 있다는 뜻으로 최단경로나 플로우 알고리즘 등에서 나온다.

  가중치가 있으면 가중치 그래프, 가중치가 없으면 비가중치 그래프라고 한다.

 

 

무향 그래프이면서 가중치 그래프이다.

 

 

 

---

 

그래프의 표현 방법

 

이 그래프를 예로 설명할 것이다.

 

 

1. 인접행렬

 

 

 

그래프에서 정점들의 연결 관계를 2차원 배열에 0과 1로 나타낸 행렬로, 2차원 배열을 이용해 구현할 수 있다. 예를 들어 다음과 같은 그래프에 대해 인접행렬로 표현해보자.

 

 

• 1번 정점은 2, 3번 정점과 인접
• 2번 정점은 1, 4, 5번 정점과 인접
• 3번 정점은 1, 6번 정점과 인접
• 4번 정점은 2번 정점과 인접
• 5번 정점은 2번 정점과 인접
• 6번 정점은 3번 정점과 인접

 

 

위와 같은 그래프를 나타내는 방법은 인접행렬을 아래와 같이 정의함으로써 만들 수 있다.

$adj[i][j]$: i번 정점과 j번 정점이 인접해 있으면 1, 그렇지 않으면 0

 

예를 들어 1번째 줄을 보면 1번 정점은 2, 3번 정점과 인접하므로 2번째, 3번째 칸만 1로 채우면 된다.

따라서 1행은 {0, 1, 1, 0, 0, 0}이 된다.

 

 

	1번	2번	3번	4번	5번	6번
1번	0	1	1	0	0	0
2번	1	0	0	1	1	0
3번	1	0	0	0	0	1
4번	0	1	0	0	0	0
5번	0	1	0	0	0	0
6번	0	0	1	0	0	0

 

 

 

인접행렬을 통해 알 수 있는 사실은 다음과 같다.

 

 

1. adj[1][1], adj[2][2], ...adj[n][n]은 모두 0이다.(자기 자신과 인접할 수 없기 때문이다.)

2. 무향 그래프의 경우에는 adj[1][1], adj[2][2], ...adj[n][n]을 이은 선(대각선)을 기준으로 인접행렬이 대칭적이다.(정점 A-

>B가 가능하면 B->A도 가능하기 때문이다.)

 

 

 

 

 

메모리 사용량: $O(N^{2})$

인접 여부 확인: $O(1)$ (정점 $u$와 $v$가 인접했는지 확인 하려면 adj[u][v]의 값만 확인하면 되기 때문)

 

 

 

 

구현은 다음과 같다.

 

int n, m; //n: 정점의 개수, m: 간선의 개수
int adj[101][101]; //인접행렬 v, 정점의 개수가 최대 100이라고 가정했다.
 
cin >> n >> m;
 
for(int i=1; i<=m; i++){ //m개의 간선 입력
    int a, b;
    cin >> a >> b; //a->b, b->a 간선 만들기
    adj[a][b]=1; //a->b 연결
    adj[b][a]=1; //b->a 연결
}

 

 

 

2. 인접 리스트

 

인접 리스트는 어떤 정점과 인접한 정점들만 리스트로써 나타내는 표현 방법이다. 즉, i번째 행에는 i번 정점과 인접한 모든 정점들의 목록이 나타나있는 것이다. 이는 단순히 2차원 배열을 0과 1로 채우는 인접행렬에 비해 메모리적으로 효율적이라는 특징이 있고, 일반적으로 정점의 개수가 많을 때 사용되는 방법이다.

 

 

 

위에서 예시로 든 그래프를 인접 리스트로 나타내면 다음과 같다. 연결되어 있는 정점들만 저장한 것으로 매우 간단하게 나타낼 수 있다.

 

 

1: [2, 3] 
2: [1, 4, 5] 
3: [1, 6] 
4: [2] 
5: [2]
6: [3]

 

 

 

 

메모리 사용량: 인접행렬보다 적음

인접 여부 확인: $O(N)$ (정점 $u$와 $v$가 인접했는지 확인하려면 $adj[u]$를 순차 탐색해야한다.)

 

 

 

 

구현

 

 

int n, m; //n: 정점의 개수, m: 간선의 개수
vector<int> adj[101]; //인접리스트 v, 정점의 개수가 최대 100이라고 가정했다.
 
cin >> n >> m;
for(int i=1; i<=m; i++){ //m개의 간선 입력
    int a, b;
    cin >> a >> b; //a->b, b->a 간선 만들기
    adj[a].push_back(b); //a번 정점과 인접한 정점들의 리스트에 b추가
    adj[b].push_back(a); //b번 정점과 인접한 정점들의 리스트에 a추가
}