[Java] Graph 그래프 / 인접 행렬 / 인접 리스트

뇌를 자극하는 알고리즘 (박상현 저)를 참고해 정리한 내용입니다.

Graph란?

객체 사이의 연결 관계를 표현할 수 있는 자료구조

정점의 집합과 간선의 집합의 결합

즉, 정점과 간선으로 이루어진 자료구조의 일종

 

G : 그래프

Vertex : = 노드(node) 또는 정점의 집합

Edge : 간선의 집합 (= link)

라고 했을 때, G = (V, E)이다.

 

 

간선으로 연결되어 있는 두 정점을 가리켜 서로 '인접(adjacent)' 또는 이웃 관계에 있다고 말한다.

 

 

(A, B), (A, D), (A, E), (B, C), (B, E), (C, D)가 서로 이웃 관계에 있다.

이렇게 간선을 통해 서로 이웃이 된 각 정점은 그래프 안에서의 길을 형성하기도 한다.

 

예를 들어 정점 A에서 정점 C까지는 A, B, C가 하나의 '경로(Path)'를 이루고, A, D, C가 또 하나의 경로를 형성한다.

경로는 길이를 가지는데, 길이는 정점과 정점 사이에 있는 간선의 수로 정의된다.

A, B, C 사이에는 간선이 (A, B), (B, C) 두 개가 있으니 길이가 2이다.

 

한편, 어느 경로가 정점 하나를 두 번 이상 거치도록 되어있다면 그 경로를 일컬어 '사이클(Cycle)'이라고 한다.

예를 들어 A, B, C, D, A에 이르는 경로가 바로 사이클이다. (시작 정점과 종료 정점이 동일)

 

 

간선으로 인해 이웃이 생기고 길(경로)이 생기며 사이클이 생긴다.

그렇기 때문에 간선은 그래프의 성격 자체를 바꾸기도 한다.

간선이 방향성을 가지면 방향성 그래프(Directed Graph)

간선에 방향성이 없으면 무방향성 그래프(Undirected Graph)

무방향 그래프와 방향 그래프

간선의 종류에 따라 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분된다.

 

무방향 그래프의 간선은 간선을 통해서 양방향으로 갈 수 있다.

정점 A와 B를 연결하는 간선은 (A, b)와 같이 정점의 쌍으로 표현한다. (A, B) = (B, A)

 

방향 그래프는 간선에 방향성이 존재하는 그래프로 일방통행길처럼 간선을 통하여 한쪽 방향으로만 갈 수 있다.

정점 A에서 정점 B로만 갈 수 있는 간선은 <A, B>로 표시한다. <A, B> ≠ <B, A>

 

V(G1) = {0, 1, 2, 3}, 

E(G1) = {(0, 1), (0, 3), (1, 3), (2, 3)}

 

V(G2) = {0, 1, 2, 3},

E(G2) = {<0, 1>, <0, 3>, <3, 1>, <2, 3>}

 

연결성(Connectivity)

무방향성 그래프 내의 두 점 사이에 경로가 존재하면 '이 두 정점이 연결되어 있다'라고 한다.

그리고 그래프 내의 각 정점들이 다른 모든 정점들과 연결되어 있으면 '이 그래프는 연결되었다'라고 한다.

연결성은 정점과 그래프 양쪽에 사용될 수 있으면서도 어느 쪽에 사용되느냐에 따라 의미는 조금 달라진다고 할 수 있다.

연결 그래프

 

무방향 그래프 G에 있는 모든 정점 쌍에 대하여 항상 경로가 존재한다면 G는 연결되었다고 하며, 연결 그래프(connected graph)라 한다.

그렇지 않은 그래프는 비연결 그래프(unconnected graph)

완전 그래프

그래프에 속해있는 모든 정점이 서로 연결외어 있는 그래프를 완전 그래프(complete graph)라 한다.

무방향 완전 그래프의 정점의 수를 n이라고 하면, 하나의 정점은 n-1개의 다른 정점으로 연결되므로 간선의 수는 n * (n - 1) / 2가 된다.

ex) 완전 그래프에서 n = 4라면 간선의 수는 (4 * 2) / 2 = 6이다.

 

부분 그래프

 

어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프를 부분 그래프(sub graph)라 한다.

그래프 G의 부분 그래프 S는 아래와 같은 수식을 만족시키는 그래프이다.

V(S) ⊆ V(G)

E(S) ⊆ E(G)

네트워크

 

간선에 가중치를 할당하게 되면 간선의 역할이 두 정점간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있으므로 보다 복잡한 관계를 표현할 수 있게 된다.

이렇게 간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프(weighted graph) 또는 네트워크(network)라 한다.

정점의 차수(degree)

그래프에서 인접 정점(adjanect vertex)이란 간선에 의해 직접 연결된 정점을 뜻한다.

무방향 그래프에서 정점의 차수(degree)는 그 정점에 인접한 정점의 수를 말한다.

ex) 정점 1의 인접 정점은 2, 3, 4, 5이며 차수는 4이다.

 

무방향 그래프에서 모든 정점의 차수를 합하면 간선 수의 2배가 된다.

왜냐하면 하나의 간선이 두개의 정점에 인접하기 때문이다.

ex) 모든 정점 차수의 합은 4 + 3 + 2 + 2 + 3 = 14, 간선은 7개

 

방향 그래프에서는 외부에서 오는 간선의 개수를 진입 차수(in-degree)

외부로 향하는 간선의 개수를 진출 차수(out-degree)라한다.

그래프의 표현 방법

그래프를 표현하는 것은 정점의 집합과 간선의 집합을 표현하는 것과 같다.

 

정점의 집합은 배열이나 리스트, 어떤 자료구조를 사용하더라도 쉽게 표현이 가능하다.

하지만 간선은 정점과 정점의 인접 관계를 나타내야 한다.

 

이러한 인접 관계를 나타내는 대표적인 방법에는 행렬을 이용하는 인접 행렬(Adjacency Matrix)과 리스트를 이용하는 인접 리스트(Adjacency List) 방법이 있다.

 

인접 행렬

정점끼리의 인접 관계를 나타내는 행렬이다.

그래프의 정점의 수를 NXN 크기의 행렬을 만든다.

행렬의 각 원소를 한 정점이라 생각하고,

한 정점과 또 다른 정점이 인접해 있는 경우(즉, 정점 상이에 간선이 존재하는 경우)에는 1, 인접해 있지 않은 경우에는 0으로 행렬에 표시하는 것이다.

 

예를 들어 정점 1은 정점 2, 3, 4, 5와 인접해 있으니 (1, 2), (1, 3), (1, 4), (1, 5)는 모두 1이다.

정점 1은 자기 자신과 인접 관계를 만들 수 없으니 (1, 1)은 0이고 (2, 2), (3, 3), (4, 4), (5, 5) 모두 0이다.

이런 식으로 나머지 정점들에 대해서도 인접 표시를 하면 우측 그림과 같은 행렬을 얻을 수 있다.

 

(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)를 따라 선을 죽 그어서 행렬을 둘로 나누어보면 인접 행렬이 주 대각선에 대해 대칭을 이루고 있다.

무방향 그래프의 경우 인접 행렬은 주 대각선에 대해 대칭을 이루는 것이 특징이다.

 

방향성을 가지는 그래프의 경우 아래와 같이 표현할 수 있다.

 

 

n개의 정점을 가지는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요하다.

그래프에 간선이 많이 존재하는 밀집 그래프(dense graph)를 표현하는 경우에는 적합하나, 그래프 내에 적은 수의 간선만을 가지는 희소 그래프(sparse graph)에는 메모리의 낭비가 크므로 적합하지 않다.

인접 행렬의 시간 복잡도 

두 정점을 연결하는 간선의 존재 여부를 O(1) 시간 안에 즉시 알 수 있다.

(정점 u와 정점 v를 연결하는 간선이 있는지를 알려면 M[u][v]의 값을 조사하면 됨)

 

정점의 차수는 O(n)

(정점 i에 대한 차수는 인접 배열의 i번째 행에 있는 값을 모두 더하면 됨)

모든 간선의 수를 알아내려면 O(n^2)

(인접 행렬 전체를 조사해야 하므로 n^2번의 조사가 필요함)

인접 리스트

각각의 정점에 인접한 정점들을 연결 리스트로 표시한 것.

 

 

 

모든 정점을 죽 늘어놓고 각 정점의 인접 정점을 옆에 나열하면 된다.

그다음에는 인접 정점들끼리 리스트로 연결한 후 각 정점에 연결한다.

 

정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 연결 리스트에 쉽게 접근할 수 있다.

 

정점의 수가 n개이고 간선의 수가 e개인 무방향 그래프를 표시하기 위해서는 n개의 연결 리스트가 필요하고,

n개의 헤더 노드와(그래프의 각 정점) 2e개의 노드가 필요하다.

따라서 간선의 개수가 적은 희소 그래프(sparse graph)의 표현에 적합하다.

 

인접 리스트의 시간 복잡도 

두 정점을 연결하는 간선의 존재 여부나 차수를 알기 위해서는 노드의 수만큼, 즉 정점의 차수만큼의 시간이 필요

(정점 i의 연결 리스트를 탐색해야 하므로 연결 리스트에 있는 노드의 수만큼, 즉 정점의 차수만큼의 시간이 필요)

 

모든 간선의 수를 알아내려면 O(n+e)

(n개의 정점과 e개의 간선을 가진 그래프에서 헤더 노드를 포함하여 모든 인접 리스트를 조사해야 하기 때문)

인접 행렬 VS 인접 리스트

인접 행렬을 이용하면 정점 간의 인접 여부를 빠르게 알 수 있지만, 인접 관계를 행렬 형태로 저장하기 위해 사용하는 메모리 양이 '정점의 크기 X N^2에 이른다는 단점이 있다.

인접 리스트는 정점 간의 인접 여부를 알아내기 위해 인접 리스트를 타고 순차 탐색을 해야 한다는 단점이 있는 반면에 정점과 간선의 삽입이 빠르고 인접 관계를 표시하는 리스트에 사용되는 메모리의 양이 적다는 단점이 있다.

 

둘 중 어느 한쪽도 압도적으로 장점이 많지는 않다.

따라서 어느 자료구조를 선택할 것인가는 작성하는 프로그램의 목적에 따라 결정하는 것이 좋다. 

그래프 탐색

하나의 정점으로부터 시작해 차례로 모든 정점들을 한 번씩 방문하는 것

그래프를 순회하는 것(그래프의 각 정점을 순회하는 것)

대표적인 기법으로 너비 우선 탐색과 깊이 우선 탐색 두 가지가 있다.

 

인접 행렬, 인접 리스트의 구현, 탐색의 방법은 관련 포스트를 확인해주세요.

참고

뇌를 자극하는 알고리즘(박상현 저)
C언어로 쉽게 풀어쓴 자료구조(개정 3판) - 생능 출판

관련 포스트

[Java] DFS 깊이 우선 탐색 - 인접 리스트 / 인접 행렬로 구현

[Java] BFS 너비 우선 탐색 - 인접 리스트 / 인접 행렬로 구현