[자료구조] 그래프(Graph)

그래프(Graph)

그래프는 연결되어있는 원소들 간의 관계를 표현한 자료구조이다.

일상 속에서의 대표적인 예시로는 지하철 노선도를 떠올릴 수 있다.

그래프 관련 용어

• 정점(vertex): 노드라고도 하며, 각 지점(위치)을 의미한다. 
• 간선(edge): 정점들을 잇는 선을 의미한다.
•  사이클(cycle): 시작 정점과 종료 정점이 동일한 경우를 의미한다.
• 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점을 의미한다. ex) A-B, C-E, C-F
• 정점의 차수(degree): 무방향 그래프에서 각 정점에서의 간선의 수를 의미한다.

그래프의 종류

1. 방향 그래프

• 간선에 방향이 존재하는 그래프
• A와 B가 연결되어 있을 때, (A, B)와 (B, A)는 다르다.

2. 무방향 그래프

• 간선에 방향이 존재하지 않는 그래프
• 한 간선을 통해 양방향 이동이 가능하다.
• A와 B가 연결되어 있을 때, (A, B)와 (B, A)가 같다.

3. 가중치 그래프

• 두 정점 간 이동을 할 때, 비용이 드는 그래프
• 방향 그래프일 수도, 무방향 그래프일 수도 있다.

4. 완전 그래프

• 모든 정점이 연결되어 있는 그래프
• 무방향 완전 그래프의 노드가 n개일 때 간선의 수는 n * (n - 1) / 2개이다.

그래프 구현

그래프를 구현하는데는 2가지 방법이 있다.

1. 인접 행렬(Adjacency Matrix)

인접 행렬은 n * n 형태의 배열 즉, 2차원 배열을 이용한다.

node1과 node2가 연결되있다는 것을 matrix[node1][node2] = true와 같은 식으로 체크해주면 된다.

fun main() {
    val nodeCount = 4
    val matrix = Array(nodeCount + 1) { BooleanArray(nodeCount + 1) }

    val edgeCount = 3
    repeat(edgeCount) { i ->
        val (node1, node2) = readLine()!!.split(" ").map { it.toInt() }
        matrix[node1][node2] = true
    }

    printMatrix(matrix)
}

private fun printMatrix(matrix: Array<BooleanArray>) {
    repeat(matrix.size) { i ->
        repeat(matrix[i].size) { j ->
            print("${matrix[i][j]} ")
        }
        println()
    }
}

무방향 그래프라면 양방향으로 연결된 것이므로 matrix[node1][node2] = true, matrix[node2][node1] = true가 되어 대칭 행렬이 된다.

• 장점
  • 구현하기 쉽다.
  • 두 정점을 연결하는 간선의 존재 여부를 O(1) 시간 복잡도 안에 확인할 수 있다.
• 단점
  • 간선의 갯수에  상관없이 n * n 크기의 배열을 만들어야 한다.
  • 그래프에 존재하는 간선의 수는 O(n²)안에 알 수 있다.

2. 인접 리스트(Adjacency List)

각 정점에 인접 정점들을 리스트로 표시해주는 방법이다.

정점의 번호만 안다면, 이 정점의 인접 정점들에 쉽게 접근할 수 있다.

fun main() {
    val nodeCount = 4
    val matrix = Array(nodeCount + 1) { mutableListOf<Int>() }

    val edgeCount = 5
    repeat(edgeCount) {
        val (node1, node2) = readLine()!!.split(" ").map { it.toInt() }
        matrix[node1].add(node2)
    }

    printList(matrix)
}

private fun printList(matrix: Array<MutableList<Int>>) {
    for(i in 1 until matrix.size) {
        println("${i}번 노드: ${matrix[i]}")
    }
}

인접행렬과 마찬가지로 무방향 그래프일 때는 matrix[node2].add(node1)까지 해줘야 한다.

• 장점
  • 각 노드에 인접한 노드를 쉽게 찾을 수 있다.
  • 그래프에 존재하는 간선의 수를 O(E) 안에 찾을 수 있다.
• 단점
  • node1과 node2가 연결되어있는 것을 확인하고 싶을 때, graph[node1]의 리스트 전체를 돌며 확인해야 한다. 즉, 정점의 차수만큼의 시간이 필요하다.