그래프(Graph)란?

수학에서, 더 구체적으로 그래프 이론에서, 그래프는 일부 객체들의 쌍들이 서로 연관된 객체의 집합을 이루는 구조라고 얘기한다.

컴퓨터에서의 그래프는 수학에서 객체 간에 짝을 이루는 관계를 자료구조로 모델링한 것이다.

 

그래프에서는 객체를 정점(Vertext) 또는 노드(Node), 점(포인트/Point) 등으로 표현하는데 보통 정점(Vertex)를 더 많이 사용하고 

두개의 객체간 어떤 관계가 있는지를 나타낼 때는 에지(Edge), 간선, 링크(Link) 등으로 표현다.

 

따라서 객체간의 관계를 이루는 집합을 그래프 G 라고 하면 이는 버텍스 집합 V와  에지의 집합 E의 순서쌍을 G = (V, E)로 나타낼수 있다.

 

G = (V, E)

▲ [출처] https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/

 

위 그림에서 버텍스 V = { 0, 1, 2, 3, 4 } 와 각 버텍스간 연결된 엣지 E = { (0,1), (1,2), (2,3) , (3,4), (0,2), (1,4), (1,3) } 를 보여주고 있다.

사실 이미 우리는 그래프를 본적이 있는데 바로 트리이다. 트리의 노드가 버텍스이고 부모/자식의 관계가 바로 엣지가 되는 것이다. 

트리외에서 실생활에서 그래프로 표현할 수 있는것은 상당히 많다. 

페이스북의 친구 관계(네트워크) 라던지 지하철 역간 호선을 연결한 맵이라던지, 전세계의 네크워크를 연결한 인터넷도 그래프로 표현하기 좋은 실예라고 볼 수 있다. 

 

 

페이스북 친구 관계(쇼셜네트워크)를 그래프로 표현

▲ [출처] https://mathematica.stackexchange.com/questions/11673/how-to-play-with-facebook-data-inside-mathematica

 

 

 

런던 지하철역을 그래프로 표현

 

▲ [출처] https://visualign.wordpress.com/2012/07/11/london-tube-map-and-graph-visualizations/

 

 

네트워크 오퍼레이션을 그래프로 관리

▲ [출처] https://neo4j.com/business-edge/managing-network-operations-with-graphs/

 

 

페이스북은 소셜네트워크를 그래프 자료구조로 저장하여 다양한 비지니스에 활용하고 있는데 이런 페이스북의 성장과 동시에 뜨게 된 것 중 하나가 그래프 DB(Graph DB) 이다. 그래프 DB는 그래프로 표현되는 자료구조를 DB로 저장 할 수 도록 해주는데  neo4j 나 카카오에서 오픈소스로 공개한 S2Graph 등이 있다. 

 

그래프를 자료구조를 코드로 구현하기전에 우리는 그래프에서 사용되는 몇가지 용어를 이해할 필요가 있기 때문에 용어부터 정리할 필요가 있다. 

 

그래프 용어(terms)

▲ [출처 ] https://www.cpp.edu/~ftang/courses/CS241/notes/graph.htm

그래프 G = (V, E) 는 정점(Vertext) or 노드(Node) or 점(포인트/Point) 집합 V 가 정점을 연결하는 에지(Edge) or 링크(Link) 로 연결된 집합 E로 구성된ㄷ. 위 그림을 예로 들면 

정점이 5개와  V = { V0, V1, V2, V3, V4} 와  에지 6개 E = { e0, e1, e2, e3, e4, e5 } 로 구성된 그래프이다.

 

▲ [출처] http://www.ritambhara.in/adjacency-matrix-implementation-of-graph-data-structure/

☞ 방향 or 무방향그래프 : 그래프에는 정점간 에지로 연결될 때 방향이 있을수도 있고 방향이 없을수도 있는데 방향이 있는 그래프를 방향그래프(Directed Graph)라하고 없는 그래프를 무방향그래프(Undirected Graph)라 한다.  방향은 보통 에지 끝에 화살표로 표현된다. 
☞  가중치(weight) : 그리고 에지마다 가중치(weight)를 지정할 수도 있다.  위 그림 (C)는 정점끼리 연결된 에지에 가중치가 지정된것을 확인 할 수 있고 가중치는 방향/무방향그래프 모두 지정 가능하다. 

☞ self-loop : 보통 다른 정점간 에지가 연결되어 있는데 에지가 자기자신을 가리키는 경우 self-loop 그래프라 하고 그 에지를 self-edge라 한다. 
☞ degree : 그래프에서 정점(or 노드)와 인접한 에지(edge) 개수를 degree 라고 하는데  그림 (A) 에서 E 정점으로 부터 에지의 수는 3개 (A, C, D) 이기 때문에 degree(E) = 3이 된다. 방향그래프에서 degree는 2가지로 나뉠수 있는데 하나는 indegree 와 outdegree 이다. indegree는 정점을 가리키는 에지를 말하고 outdegree는 정점에서 나가는 에지를 말한다. 
그림(B) 방향그래프에서 정점 E쪽으로 들어오는 에지의 indegree는 A, D 2개이고 나가는 에지의 outdegree는 C 하나가 되는 것이다.