[알고리즘] Graph 그래프 : 필수 기본 정리 - 가중치, 방향, 무방향 그래프, 인접리스트, 인접행렬 구현

목차

 

그래프(Graph)

그래프는 objects의 관계를 나타내는 데이터 구조입니다. 이렇게 관계를 나타내는 이유는 무엇일까요? 두 object의 연결은 둘이 서로 알고 있다는 뜻입니다. 서로 안다는 양방향성 관계를 뜻합니다.

 

그래프는 정점 (Vertices)와 변(Edges)들로 이루어져 있습니다. 아래와 같이 꼭짓점은 노드이고 선은 각 노드들을 이어줍니다. 

정점과 변

그래프 종류

그래프 종류에는 3가지가있습니다. 아래 각 그래프의 특징들을 살펴보겠습니다. 

다이어그램	설명
가중치 그래프	가중치그래프는 옆에 이미지와 같이, 정점 사이의 코스트나 거리등을 나타내어 활용됩니다.  예를 들어 도쿄에서 워싱턴 디씨를 거쳐 샌프란시스코를 간다면 총 300+ 337불이 들게됩니다.
방향 그래프	방향그래프는 말그대로 방향성이있는 그래프입니다. 그리고 각 변들은 방향성을 가지고있게됩니다.  예를 들어보겠습니다. 싱가폴과 도쿄 사이에 왕복 비행기가있습니다. 도쿄에서 워싱턴으로 가는 항공편은있지만 돌아오는 비행기는 없습니다.
무방향 그래프	무방향 그래프는 방향성이 없는 그래프입니다. 쌍방통행이 가능한 변을 가지고있다고 할수있습니다.  옆에 그림을 예로 들자면 변으로 연결되있다면 왕복으로 비행기가 있다는 뜻입니다.

 

그래프 인터페이스 생성

그래프 인터페이스를 구현해주겠습니다. 

interface Graph<T> {
	fun createVertex(data: T): Vertex<T> 
    
    fun addDirectedEdge(source:Vertex<T>, destination: Vertex<T>, weight: Double?)
    
    fun addUndirectedEdge(source: Vertex<T>, destination: Vertex<T>, weight: Double?)
    
    fun add(edge: EdgeType, source: Vertex<T>, destination: Vertex<T>, weight: Double?)
    
    fun edges(source: Vertex<T>): ArrayList<Edge<T>>
    
    fun weight(source: Vertex<T>, destination: Vertex<T>): Double?
    
}

enum class EdgeType{
	DIRECTED, UNDIRECTED
}

인터페이스가 가지고있는 함수들에 역할을 확인해보겠습니다. 

1. createVertex(): 정점(vertex)을 만들어 그래프에 추가합니다. 

2. addDirectedEdge(): 방향성을 가진 변을 두 정점 사이에 추가합니다. 

3. addUndirectedEdge(): 방향성이 없는 변을 두정점 사이에 추가합니다. 

4. add(): 변을 정점사이에 추가합니다. 

5. edges(): 지정된 정점에서 변이 어디로 향하는지 도착 정점들을 반환합니다. 

6. weight(): 변에 지정된값을 반환합니다. 위에서 가중치 그래프를 나타냈을 때 각 변은 cost를 나타내었습니다. 

 

정점(Vertex) 생성

data class Vertex<T>(val index: Int, val data:T)

정점은 인덱스 값과 데이터 값을 가지고있습니다

 

변 (Edges) 생성

data class Edge<T>(
    val source: Vertex<T>,
    val destination: Vertex<T>, 
    val weight:Double? = null
)

weight은 선택적으로 넣어주게 됩니다. weight값이 없을 수 있기 때문입니다. 

 

 

인접 리스트

인접 리스트는 그래프의 연결 관계를 Vector배열로 나타내는 방식입니다. 먼저 방향성이 있는 변을 가질 때 인접 리스트를 확인해보겠습니다. 

방향 그래프

위와 같이 3은 아무 노드도 없는 걸 확인할 수 있는데 이 이유는, 3이 가리키는 방향의 변이 없기 때문입니다. 

---

다음으로는, 무향 그래프일 때입니다. 쌍방향으로 가리키기 때문에 서로 연결돼있습니다. 

무향 그래프

인접 리스트 구현

맵을 이용 하여, 인접 리스트를 구현해야 합니다. 아래 코드를 살펴보겠습니다. 

class AdjacencyList<T> : Graph<T>{
    private val adjacencies: HashMap<Vertex<T>>,ArrayList<Edge<T>> = HashMap()
    //more to come
}

맵에서 변 값을 저장하게 됩니다. 이제 다음으로 정점을 만들어주겠습니다. 

 

 

정점 생성 함수 구현

이 함수는 인접 리스트 클래스 안에 오버라이드 해줘야 합니다. 

override fun createVertex(data: T): Vertex<T> {
	val vertex = Vertex(adjacencies.count(), data)
    adjacencies[vertex] = ArrayList()
    return vertex
}

새로운 vertex를 만든 후 반환합니다. 

 

방향, 무방향 변(Directed Edge, Undirected Edge) 구현

방향 변 무방향 변(Directed Edge, Undirected Edge) 구현

 

방향 변/ 무방향 변

방향 변 구현

override fun addDirectedEdge(source: Vertex<T>, destination: Vertex<T>, weight:Double?) {
    val edge = Edge(source, destination,weight)
    adjacencies[source]?.add(edge)
}

무 방향 변 구현

무방향 변은 쌍방향 변이기 때문에, 방향 변을 두 개 추가해줍니다. 

fun addUndirectedEdge(source: Vertex<T>,destination: Vertex<T>, weight: Double?) {
    addDirectedEdge(source, destination, weight)
    addDirectedEdge(destination, source, weight)
}

 

이제 만들어진 변을 추가해주도록 하겠습니다. 

fun add(edge: EdgeType,source: Vertex<T>, destination: Vertex<T>, weight: Double?) {
	when(edge) {
    	EdgeType.DIRECTED -> addDirectedEdge(source, destination, weight)
        EdgeType.UNDIRECTED -> addUndirectedEdge(source, destination, weight)
    }
}

add 함수는 방향이 있는 변을 쓸지 방향 없는 변을 쓸지 정해줍니다. 

 

변 검색 구현

그래프에 있는 변 값들을 검색합니다. 변들이 있다면 리스트로 반환하고 없다면, null을 반환합니다. 

override fun edges(source: Vertex<T>) = 
	adjacencies[source]?: arrayListOf()

변 값 검색

싱가포르에서 도쿄를 가는데 얼마나 들까요? 아래와 같이 변 값을 탐색할 때 이 함수가 유용합니다. 

override fun weight(source: Vertex<T>, destination: Vertex<T>): Double? {
	return edges(source).firstOrNull{
    	it.destination == destination}?.weight
    }
}

 

인접 리스트 구상화 구현

인접 리스트가 어떻게 되어있는지 보기 위해 코드로 보겠습니다. 이 코드를 복사해서 넣어주세요

override fun toString(): String {
    return buildString { //1
    	adjacencies.forEach { (vertex, edges) -> //2
        	val edgeString = edges.joinToString {
            	it.destination.data.toString() //3
            } append("${vertex.data} --> [$edgeString ] \n") //4
        	
        }
    }
}

 

네트워크 구현

지금까지 만들어준 코드들로 아래 네트워크 그래프를 구현해보겠습니다. 

항공편과 가격을 나타낸 그래프

위 그래프를 구현하기 위해 먼저 메인 문에 코드를 작성하겠습니다. 

val graph = AdjacencyList<String>()
val singapore = graph.createVertex("Singapore")
val tokyo = graph.createVertex("Tokyo")
val hongKong = graph.createVertex("Hong Kong")
val detroit = graph.createVertex("Detroit")
val sanFrancisco = graph.createVertex("San Francisco")

val washingtonDC = graph.createVertex("Washington DC")
val austinTexas = graph.createVertex("Austin Texas")
val seattle = graph.createVertex("Seattle")
graph.add(EdgeType.UNDIRECTED, singapore, hongKong, 300.0)
graph.add(EdgeType.UNDIRECTED, singapore, tokyo, 500.0)
graph.add(EdgeType.UNDIRECTED, hongKong, tokyo, 250.0)
graph.add(EdgeType.UNDIRECTED, tokyo, detroit, 450.0)
graph.add(EdgeType.UNDIRECTED, tokyo, washingtonDC, 300.0)
graph.add(EdgeType.UNDIRECTED, hongKong, sanFrancisco, 600.0)
graph.add(EdgeType.UNDIRECTED, detroit, austinTexas, 50.0)
graph.add(EdgeType.UNDIRECTED, austinTexas, washingtonDC, 292.0)
graph.add(EdgeType.UNDIRECTED, sanFrancisco, washingtonDC, 
337.0)
graph.add(EdgeType.UNDIRECTED, washingtonDC, seattle, 277.0)
graph.add(EdgeType.UNDIRECTED, sanFrancisco, seattle, 218.0)
graph.add(EdgeType.UNDIRECTED, austinTexas, sanFrancisco, 297.0)
println(graph)

이제 위 코드를 실행해주면 아래와 같은 결과 값을 얻을 수 있습니다. 

Detroit ---> [ Tokyo, Austin, Texas ]
Hong Kong ---> [ Singapore, Tokyo, San Francisco ]
Singapore ---> [ Hong Kong, Tokyo ]
Washington, DC ---> [ Tokyo, Austin, Texas, San Francisco, 
Seattle ]
Tokyo ---> [ Singapore, Hong Kong, Detroit, Washington, DC ]
San Francisco ---> [ Hong Kong, Washington, DC, Seattle, Austin, 
Texas ]
Austin, Texas ---> [ Detroit, Washington, DC, San Francisco ]
Seattle ---> [ Washington, DC, San Francisco ]

이렇게 각 정점마다 항공편이 뭐가 있는지 확인할 수 있습니다. 

 

다른 함수를 사용해서 다양한 정보를 얻어을수있습니다. 싱가포르에서 도쿄 가는데 얼마나 들까요? 다음 함수를 통해 알 수 있습니다. 

println(graph.weight(singapore, tokyo))

 

인접 행렬

인접 행렬은 matrix를 이용하여 그래프에 정점을 나타냅니다. 행과 열에 변의 값을 가지고 있게 됩니다. 좀 더 쉬운 설명을 위해 다이어그램을 통해 살펴보겠습니다. 

그래프

위와 같은 그래프를 인접 행렬을 통해 만들어보겠습니다. 

인접행렬

테이블 안에 0이 의미하는 것은 두 행과 열 사이에 연결이 없음을 의미합니다. 그리고 숫자가 있다면, 연결이 있다는 의미와 그 숫자만큼의 변 값을 가지고 있음을 의미합니다. 

 

위 인접 행렬의 테이블을 읽어보겠습니다. 

[0][1] 싱가포르에서 홍콩 가는 비행기표는 $300입니다. 

[2][1] 도쿄에서 홍콩 가는 비행기표는 $0입니다. 비행기표가 없습니다.  

[1][2] 홍콩에서 도쿄 가는 비행기표는 $250입니다. 

[2][2] 도쿄에서 도쿄 가는 비행기는 없기 때문에 0입니다. 

 

 

인접 행렬 구현

class AdjacencyMatrix<T> : Graph<T> {
   private val vertices = arrayListOf<Vertex<T>>()
   private val weights = arrayListOf<ArrayList<Double?>>()
   // more to come ... 
}

 

정점 구현

새로운 정점을 만들려 한다면 인접 행렬은 어떻게 구현해야 할까요? 아래 코드 설명 후 정점이 만들어지는 과정을 설명하겠습니다. 

override fun createVertex(data:T): Vertex<T> {
    val vertex = Vertex(vertices.count(), data)
    vertices.add(vertex) //1
    weights.forEach {
    	it.add(null)//2
    }
    weights.add(arrayListOf())//3
    return vertex
}

override fun createVertex(data:T): Vertex<T>{
	val vertex = vertex(vertex.count(),data)
    vertices.add(vertex)//1
    weight.forEach{
    	it.add(null)//2
    }
    val row = ArrayList<Double?> vertices.count()
    repeat(verticies.count()) {
    	row.add(null)
    }
    weights.add(row)//3
    return vertex
}

1. 새로운 정점 array를 추가합니다.

2. 모두 null값인 행값이 새로 생기게 됩니다. 

3. 모두 null값인 열도 추가합니다. 

 

변 구현

인접 행렬에서 변 구현입니다. 인접 행렬 클래스 안에 오버라이드 해주세요.

override fun addDirectedEdge (
	source: Vertex<T>, 
    destination: Vertex<T>,
    weight: Dobule?
) {
	weights[source.index][destination.index] = weight
}

 

정점이 가리키는 변들 검색

아래 함수를 인접 행렬 클래스 안에 오버라이드 해줍니다. 

override fun edges(source: Vertex<T>): ArrayList<Edge<T>> {
   val edges = arrayListOf<Edge<T>>()
   (0 until weights.size).forEach { column ->
   val weight = weights[source.index][column]
     if (weight != null) {
       edges.add(Edge(source, vertices[column], weight))
     }
   }
   return edges
}

변들이 가진 값 검색 구현

override fun weight(
     source: Vertex<T>, 
     destination: Vertex<T>
   ): Double? {
   return weights[source.index][destination.index]
}

 

인접행렬 구상화 구현

인접 행렬이 구현된걸 visualize 하기 위해 아래 코드를 붙여 넣어주겠습니다. 

  override fun toString(): String {
     // 1
     val verticesDescription = vertices.joinToString("\n") { "$
     {it.index}: ${it.data}" }

     // 2
     val grid = arrayListOf<String>()
     weights.forEach {
     var row = ""
     (0 until weights.size).forEach { columnIndex ->
         if (columnIndex >= it.size) {
            row += "ø\t\t"
         } else {
            row += it[columnIndex]?.let { "$it\t" } ?: "ø\t\t"
       }
     }
     grid.add(row)
   }
   val edgesDescription = grid.joinToString("\n")
   // 3
   return "$verticesDescription\n\n$edgesDescription"
}
override fun toString(): String {
     // 1
     val verticesDescription = vertices
        .joinToString(separator = "\n") { "${it.index}: ${it.data}" }
     // 2
     val grid = weights.map { row ->
         buildString {
         (0 until weights.size).forEach { columnIndex ->
           val value = row[columnIndex]
           if (value != null) {
              append("$value\t")
           } else {
              append("ø\t\t")
           }
        }
     }
   }
   val edgesDescription = grid.joinToString("\n")
   // 3
   return "$verticesDescription\n\n$edgesDescription"
}

 

네트워크 구현

위에서 썼던 그래프를 인접 행렬로 다시 구현해보겠습니다. 

메인 문에 val graph = AdjacencyList()를 아래 코드로 바꿔주면 됩니다.

val graph = AdjacencyMatrix<String>()

나머지 코드는 같기 때문에, 결과를 살펴보겠습니다. 

 

 

그래프 분석

인접 리스트와 인접 행렬을 다뤄보았습니다. 두 개의 오퍼레이션은 각기 다른 속도를 가지고 있는데요 아래 테이블을 확인해보겠습니다. 

Operation	Adjacency List	Adjacency Matrix
메모리사용	0(V+E)	0(V^2)
정점 추가	0(1)	0(V^2)
변 추가	0(1)	0(1)
변,변값 탐색	0(V)	0(1)