그래프 정의
일렬로 나열되어 있는 선형구조와는 달리, 일렬로 나열되어 있지 않은 비선형구조 중 하나.
그래프는 데이터를 나타내는 정점(Vertex) 혹은 Node (노드), 데이터들간의 관계를 나타내는 간선인 Edge 가 존재한다.
각 정점에 연결된 간선의 개수는 차수(Degree) 라고 부른다.
표현식은 G(Graph) = (V(Vertex), E(Edge)) 로 나타낸다.
그래프의 특징에 따른 종류
1. 방향성 (Directedness)
그래프의 간선 (Edge) 에 방향이 존재하냐 존재하지 않느냐에 종류가 나뉜다.
- 무방향성 그래프 (Undirected Graph)
- 간선에 방향이 없으며, 두 정점 (Vertex 혹은 Node) 는 양방향 연결 상태이므로, A - B. 즉, A 에서 B로, B에서 A로 이동이 가능하다.
- ex) 페이스북 친구 관계
- 방향성 그래프 (Directed Graph)
- 간선에 방향이 존재하며, 한 방향으로만 이동이 가능한 상태.
- ex) 인스타그램 팔로우
2. 가중치 (Weight)
간선에 가중치 (숫자값) 이 존재하는지에 따라 바뀐다.
-
비가중치 그래프 (Unweighted Graph)
- 모든 간선이 동일한 가중치를 가지기 때문에 별도의 가중치 값을 가지지 않는다.
- 암묵적으로 가중치가 1이라고 간주한다.
-
가중치 그래프 (Weighted Graph)
각 간선에 숫자 값 (비용, 거리 등등) 이 부여된다.
3. 순환성 (Cycle)
특정 정점(Vertex, Node) 에서 출발해 다른 정점들을 거쳐 다시 자기 자신으로
돌아올 수 있는 경로를 의미
- 순환 그래프 (Cyclic Graph)
- 그래프 내에 하나 이상의 사이클이 존재하는 그래프
- 위 이미지는 1 에서 출발하여 1로 돌아올 수 있으므로 순환 그래프이다.
- 비순환 그래프 (Acyclic Graph)
- 그래프 내에 사이클이 하나도 존재하지 않는 그래프
- 위의 이미지는 DAG (Directed Acyclic Graph) 라고 불리는 방향성 비순환 그래프이다.
- 비선형 구조인 Tree 는 무방향성 비순환 연결 그래프 이다.
4. 연결성 (Connectivity)
그래프의 모든 정점들이 도달 가능한지에 따라 분류된다.
-
연결 그래프
- 그래프 내의 임의의 두 정점을 선택했을 때, 그 두 정점 사이에 항상 경로가 존재하는 그래프
- 어떤 정점에서 출발하든 다른 모든 정점에 도달이 가능하다.
- 0과 3을 선택하는 경우, 0과 3의 경로가 존재하기에 연결된다.
-
비연결 그래프
- 그래프 내에 서로 도달할 수 없는 정점 쌍이 존재하는 그래프
- 두 개 이상의 연결 컴포넌트가 존재하는 경우
-
완전 그래프
모든 정점들이 서로 직접적인 간선으로 빠짐없이 연결되어 있는 그래프
그래프를 표현하는 법
- 인접 리스트 (Adjacency List) 방식 (추천되는 방식)
- 각 정점마다 연결된 이웃들의 목록(List) 를 저장하는 방식.
- List<MutableList<*>> 형식이다.
/*
* 인접 리스트 방식
* */
fun adjList(){
/*
* 비가중치 그래프
* */
fun unWeightGraph(){
val adjList = Array(5){ mutableListOf<Int>() }
/*
* 방향 그래프인 경우 Vertex 1에 3 만 추가.
* */
adjList[1].add(3)
// 무방향 그래프인 경우 Vertex 3 에 Vertex 1 을 추가.
adjList[3].add(1)
}
/*
* 가중치 그래프
* */
fun weightGraph(){
data class Edge(val to: Int, val weight: Int)
/*
두 가지 방식으로 사용 가능
* */
val adjList = Array(5){ mutableListOf<Edge>() }
val adjList2 = Array(5){ mutableListOf<Pair<Int, Int>>() }
// 방향 그래프
adjList[1].add(Edge(3, 4))
adjList2[1].add(Pair(3, 4))
// 무방향 그래프인 경우 Edge(to = 3, weight = 4) 도 추가하여 양방향 연결
adjList[3].add(Edge(1, 4))
adjList2[3].add(Pair(1, 4))
}
}- 인접 행렬 방식
/*
* 인접 행렬 방식
* */
fun adjMatrix(){
/*
* 비가중치 그래프
* */
fun unWeightGraph(){
/*
* adjMatrix[1번째정점][2번째정점] = 1 (연결) 0(미연결) 로 정의
* */
val adjMatrix = Array(5){ IntArray(5) }
// 방향 그래프
adjMatrix[1][3] = 1
// 무방향 그래프인 경우 [3][1] 도 추가하여 양방향 연결
adjMatrix[3][1] = 1
}
/*
* 가중치 그래프
* */
fun weightGraph(){
// 연결되지 않았음을 뜻할 변수
val inf = Int.MAX_VALUE
// 자기 자신은 0으로 설정하고 나머지는 모두 미연결 상태로 초기화.
val adjMatrix = Array(5){ row -> IntArray(5){ col -> if(row != col) inf else 0} }
// 방향 그래프. 간선의 가중치는 7
adjMatrix[1][3] = 7
// 무방향 그래프인 경우 [3][1] 에도 값을 추가하여 양방향 설정. 간선의 가중치는 7
adjMatrix[3][1] = 7
}
}왜 인접행렬 방식의 단점
- 메모리가 낭비된다.
인접 리스트의 경우 Array<MutableList<*>> 로 구현되고, 인접 행렬의 경우 Array<Array<*>> 형식으로 구현된다.
N = 2^31 개가 존재한다고 생각해보자.
수열 Vertex = 1 ... N 일때 각 Vertex 와 연결되는 다른 Vertex 가 4개 뿐이라면 인접 리스트의 경우 각각 2^31 * 4 만큼의 공간만을 필요로 하지만, 인접 행렬의 경우 2^31 * 2^31 - 1 만큼의 공간을 필요로 한다.
즉, 메모리의 낭비가 심해진다.
- 가중치가 존재하는 경우 "연결되지 않음" 을 표시하기 위한 처리가 필요하다.
인접 리스트에서는 원소가 존재하지 않는 경우 미연결 상태였지만, 인접 행렬에서는 기본적으로 1, 0으로 연결상태를 나타낸다.
비가중치 인접 행렬의 경우 위처럼 1, 0으로 연결상태를 나타내지만, 만약 가중치가 존재한다면?
0이나 1이라는 숫자가 미연결을 나타내는지, 연결을 나타내는지, 가중치를 나타내는지 알기가 쉽지 않을 것이다.
위와 같은 이유로 대체로 많은 방식에서는 인접 리스트 방식을 추천하는 것이다.
