그래프(graph)의 기본 개념(feat.kotlin)

그래프의 정의

vertex와 edge로 구성된 한정된 자료구조를 의미한다.

vertex는 정점, edge는 정점과 정점을 연결하는 간선

 

기본적으로 알아야 될 용어 및 정의

 

path 경로 : 한 정점에서 다른 정점 까지의 경로

degree 차수: 하나의 정점에 연결된 간선의 개수

cycle 순환, 회로:  경로의 시작과 끝이 동일한 것

weight, cost, 가중치: 한 정점에서 다른 정점을 연결하는 간선에 부여된 비용.

 

* 방향성 유무

무방향 즉, 양방향 이동이 가능하다.

방향성 있다 u --> v 는 되지만, u <-- v 는 안됨.

 

그래프의 표현.

1. 인접 리스트(Adjacency List)

- 각 정점을 기준으로 연결된 정점을 기록한다.

- 한 정점에서 연결된 정점만을 저장하기에 graph 탐색에 있어 유용하다.

val n = 5
val adjList = Array(n + 1) { mutableListOf<Int>() }
fun main() {

    // 정점 1에 연결된 2, 5 정점 추가
    adjList[1].add(2)
    adjList[1].add(5)

    // 정점 2에 연결된 1, 3, 4, 5 정점 추가
    adjList[2].add(1)
    adjList[2].add(3)
    adjList[2].add(4)
    adjList[2].add(5)

    // 정점 3에 연결된 2, 4 정점 추가
    adjList[3].add(2)
    adjList[3].add(4)

    // 정점 4에 연결된 2, 3, 5 정점 추가
    adjList[4].add(2)
    adjList[4].add(3)
    adjList[4].add(5)

    // 정점 5에 연결된 1, 2 정점 추가
    adjList[5].add(1)
    adjList[5].add(2)
    adjList[5].add(4)

    for (i in 1 until adjList.size){
        println("vertex ${i}에 연결된 ${adjList[i].joinToString(",")}")
    }
}

2. 인접 행렬(Adjacency Matrix)

-  간선을 중심으로 두 정점이 연결되어 있는 상태를 표현한다.

- 임의 두 정점의 연결여부를 쉽게 알 수 있다.

 

val n = 5
val adjMatrix = Array(n + 1) { IntArray(n + 1) { 0 } }
fun main() {

    // 1--2
    adjMatrix[1][2] = 1
    adjMatrix[2][1] = 1

    // 2--3
    adjMatrix[2][3] = 1
    adjMatrix[3][2] = 1

    // 2--5
    adjMatrix[2][5] = 1
    adjMatrix[5][2] = 1

    // 2--4
    adjMatrix[2][4] = 1
    adjMatrix[4][2] = 1

    // 3--4
    adjMatrix[3][4] = 1
    adjMatrix[4][3] = 1

    // 4--5
    adjMatrix[4][5] = 1
    adjMatrix[5][4] = 1

    // 5--1
    adjMatrix[1][5] = 1
    adjMatrix[5][1] = 1


    for (i in 1 until adjMatrix.size){
        for (j in 1 until adjMatrix[i].size){
            print("${adjMatrix[i][j]} ")
        }
        println()
    }

}

공간복잡도

인접리스트 (V + E)

인접행렬  (V^2)

 - 인접 리스트는 실제로 연결이된 노드들만 저장을 하지만, 인접 행렬은 모든 연결상태를 표현하기 위해 공간을 조금더 많이 사용한다.

 

시간복잡도 

 

특정 두 노드 A B의 연결상태 확인할때,

 

인접리스트 : O(V)

인접행렬 : O(1)

 

연결된 간선을 이동(탐색)할때,

 

인접리스트 : O(V + E)

인접행렬 : O(V^2)