그래프 (1) : SNS가 이거에요

이번 포스팅에서는 데이터 간의 관계에 특화된 자료구조인 그래프에 대해서 이야기해 보겠습니다.

---

1. 그래프란?

 

그래프는 관계를 표현하는데 특화된 자료구조로서 데이터 간 연결 상태를 쉽게 보여줍니다.

 

 

그래프에서는 각각의 구성 요소를 가리키는 단어가 존재합니다.

 

그래프의 노드를 정점(vertex), 그 정점을 연결하는 선을 간선(edge)라고 부릅니다.

 

간선으로 연결된 정점들은 서로 인접한다(adjacent)라고 말합니다.

 

그리고 인접한 정점들을 가리켜 이웃(neighbor)라고 부릅니다.

 

그래프에서는 다른 정점과 연결되지 않은 정점이 존재할 수 있습니다.

 

모든 정점이 연결되어있는 그래프를 가리켜 연결 그래프(connected graph)라고 부릅니다.

 

 

---

 

2. 방향 그래프

 

SNS를 예로 들어보면 A라는 사람이 B를 팔로우하고 있더라고 B는 A를 팔로우하지 않은 상태 일 수 있습니다.

 

이처럼 항상 상호 관계가 아니며 간선이 방향을 가지고 있는 그래프를 방향 그래프(directed graph)라고 합니다.

 

 

---

 

3. 그래프 의 코드 구현

 

이제 객체 형태로 그래프 (Undirected Graph)를 구현해 보겠습니다.

class Vertex {
    data
    // 인접 Vertex 배열
    groupOfAdjacentVertices


    constructor(data) {
        this.data = data
        this.groupOfAdjacentVertices = []
    }

    AddAdjacentVertex(vertex) {
        // 상호간 연결 도중 무한 Loop 방지
        if (this.groupOfAdjacentVertices.includes(vertex)) return

        this.groupOfAdjacentVertices.push(vertex)
        // 상호간 간선 연결
        vertex.groupOfAdjacentVertices.push(this)
    }
}

 

Vertex 객체에서 다른 Vertex 객체를 연결 할 때에 방향이 없는 그래프이기 때문에 상호 연결을 해주었습니다.

 

---

마치며

이번 포스트에서는 그래프에 대해서 알아보았습니다.
실생활에 밀접한 SNS에서 사용되는 자료 구조라 더 흥미롭게 살펴볼 수 있었습니다.
다음 포스트에서는 이제 이렇게 만들어진 그래프를 탐색하는 방법에 대해 알아보도록 하겠습니다.