[DS] 그래프란?

그래프는 도표라는 뜻이 있다. 자료구조에서도 비슷한 의미를 갖는 건가?

위키백과에서 설명하는 그래프는 어떤 내용인지 확인해봤다.

 

https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 

그래프 (자료 구조) - 위키백과, 우리 모두의 백과사전

그래프는 vertex와 edge로 구성된 한정된 자료구조다. vertex는 정점, edge는 정점과 정점을 연결하는 선이다. 컴퓨터 시스템에 그래프를 저장하는 법은 여러가지가 있다. 자료구조는 그래프 구조와 그래프 관리에 쓰이는 알고리즘에 영향받는다. 이론적으로 그래프는 리스트, 행렬 구조 중의 하나로 구별 가능하다. 하지만 실제 적용에 있어서 최적의 자료구조는 이 두 구조의 조합된 형태를 띤다. 리스트 구조는 종종 sparse graphs에 적합하며 적은 메모리 공간을 요구한다. 행렬 구조는 많은 메모리를 요구하지만 더 빠른 접근을 제공한다

 

대충 정점이라 불리는 것이 있으면 이걸 선으로 이어놓은 형태의 배열, 리스트로 구현될 수 있는 자료구조가 그래프인 것 같다. 위키백과에서 대충 알았으니 다른 블로그를 보면서 확인해보자.

 

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

[자료구조] 그래프(Graph)란 - Heee's Development Blog

단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아놓은 자료구조. 연결돼 있는 객체 간의 관계(지도, 지하철 노선도의 최단 경로, 전기회로 소자들, 도로, 선수 과목 등)를 표현할 수 있는 자료구조다. 그래프는 여러 개의 고립된 부분 그래프(Isolated Subgraphs)로 구성될 수 있다

그래프 관련 용어)

정점(vertex) : 위치라는 개념. node라고도 부른다
간선(edge) : 위치 간의 관계. node를 연결하는 선이고 link, branch라고도 부른다
인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수. 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수 x 2
진입 차수(in-degree) : 방향 그래프의 외부에서 오는 간선의 수. 내차수라고도 부름
진출 차수(out-degree) : 방향 그래프에서 외부로 향하는 간선의 수. 외차수라고도 부름. 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
경로 길이(path length) : 경로를 구하는 데 사용된 간선의 수
단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우
사이클(cycle) : 단순 경로의 시작 정점, 종료 정점이 동일한 경우

그래프의 특징)

- 네트워크 모델이다
- 2개 이상의 경로가 가능하다. 즉 노드들 사이에 무방향 / 방향에서 양방향 경로를 가질 수 있다
- self-loop 뿐 아니라 loop, circuit 모두 가능하다
- 루트 노드란 개념이 없다
- 부모자식 관계라는 개념이 없다
- 순회는 DFS나 BFS로 이뤄진다
- 그래프는 순환(Cycle) 혹은 비순환(Acyclic)이다
- 그래프는 크게 방향 그래프, 무방향 그래프가 있다
- 간선의 유무는 그래프와 다르다

무방향 그래프 : 무방향 그래프의 간선은 간선을 통해 양 방향으로 갈 수 있다. 정점 A, B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. (A, B)는 (B, A)와 같다

방향 그래프 : 간선에 방향성이 존재하는 그래프. A -> B로만 갈 수 있는 간선은 <A, B>로 표현한다. <A, B>와 <B, A>는 다르다

 

https://coding-factory.tistory.com/610

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?

그래프는 정점, 간선으로 이뤄진 자료구조다. 정점 간의 관계를 표현하는 조직도라고도 볼 수 있다. 그런 면에서 트리는 그래프의 일종인 셈이다. 다만 트리와는 달리 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있으며 루트 노드, 부모와 자식이란 개념이 없다. 또한 그래프는 네트워크 모델, 즉 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다. 실생활에서 다양한 예를 그래프로 표현할 수 있다. 대표적으로 지하철 노선도, 도심의 도로 등이 있다. 그래프를 순회하는 방식인 DFS, BFS를 잘 알아둬야 한다

 

아래는 2차원 배열을 통해 그래프를 구현한 예제다.

 

https://medium.com/depayse/kotlin-data-structure-graph-135edd3646ae

[Kotlin] Graph

fun main() {
    // 인접 행렬로 graph 만들기
    val graph = arrayOf(
        arrayOf(0, 1, 0, 1, 0),
        arrayOf(1, 0, 1, 0, 0),
        arrayOf(0, 1, 0, 0, 0),
        arrayOf(1, 0, 0, 1, 1),
        arrayOf(0, 1, 0, 1, 0)
    )

    // graph 출력
    for ((index1, adjacent) in graph.withIndex()) {
        // 기준 노드
        val criteriaNode = when (index1) {
            0 -> 'A'
            1 -> 'B'
            2 -> 'C'
            3 -> 'D'
            4 -> 'E'
            else -> 'X'
        }
        // 기준 노드 출력
        print("$criteriaNode : ")
        for ((index2, connected) in adjacent.withIndex()) {
            // 기준 노드와 연결된 노드만 출력
            if (connected == 1) {
                val connectedNode = when (index2) {
                    0 -> 'A'
                    1 -> 'B'
                    2 -> 'C'
                    3 -> 'D'
                    4 -> 'E'
                    else -> 'X'
                }
                print("$connectedNode ")
            }
        }
        println()
    }
}