Graph

Tree를 공부하면서 비선형 구조에 대해 공부를 했었다. 비선형 구조는 데이터가 순서를 따르지 않는다는 것이다. 적어도 배열, 링크드 리스트처럼 명백한 숫자는 아니다. 트리는 루트 노드에서 시작해서 다른 노드로 연결했었다. 그래서 하위 트리가 포함되는 재귀적인 특성을 가졌다. 트리에서는 이진 탐색 트리와 같이 모양, 순서에 따라 나눴다. 우리가 사용하기에 효율적인 트리들은 지켜야하는 규칙들이 있었다.

하지만 우리가 이 규칙을 아예 안쓴다면 어떨까? 트리의 개념에서는 안될 것이라 생각하지만 그래프의 개념에서는 다르다.

트리는 더 많은 규칙을 따라야 하는 제한된 유형의 그래프에 불과하다. 그래프와 트리의 다른 점은 트리는 루트 노드에서 자식 노드로 한 방향으로만 흐르고 루프 또는 사이클이 존재할 수 없다. 그래프는 루트 노드의 개념이 존재하지 않는다. 그리고 루프나 사이클이 존재할 수 있다. 또 방향이 있을수도 있고 없을 수도 있다. 

 

방향이 있는 그래프와 없는 그래프

그래프에는 그래도 반드시 지켜야하는 한 가지 특성있다. 

모든 그래프는 항상 최소한 하나의 단일 노드가 있어야 한다. 노드가 하나뿐인 그래프는 싱글톤 그래프라고 한다.

그래프에선 노드 간 연결을 edge( or link ) 라고 한다. 이 엣지는 다양한 유형이 있는데 그래프를 인식하고 정의할 때  매우 중요하다. 이 엣지에는 두 가지 유형이 있다. 방향이 있거나 없거나 이다.

방향이 있는 엣지는 A -> B로 연결된다. 그럼 A에서 B로만 이동할 수 있는 것이다. 하지만 방향이 없는 엣지는 A->B가 연결되면 B->A도 이동이 가능하다. 엣지에 방향이 있는 그래프를 방향 그래프, 반대를 방향이 없는 그래프라고 한다.

 

이게 왜 중요할까?

그래프에서 방향이 중요한 이유

사실 그래프는 실제로 수학과 그래프 이론이라는 그래프 연구에서 비롯된 것이다. 수학 용어로 그래프를 순서쌍으로 설명한다. 좌표계에서 (x,y) 좌표에대해 배웠을 것이다. x, y 대신 그래프의 일부가 정점(노드)의 경우 V, 엣지의 경우 E이다. 그래프에 대한 수학적 정의는 G = (V, E)이다. 하지만 그래프에 노드와 간선이 두 개 이상있다면 어떤 식으로 작동하는 걸까? 순서쌍 (V, E)는 실제로 정점 세트와 엣지 세트라는 두 개의 객체로 구성되어 작동한다. 예를 들어, 무방향 그래프에서 노드가 4개가 있고 엣지가 6개가 있다면 { V1, V2, V3, V4 } 와 같은 정점 세트와 { {V1, V2}, {V2, V3}, {V3, V4}, {V4, V1}, {V1, V3}, {V2, V4}} 와 같은 엣지 세트가 있을 것이다. 무방향 그래프니까 출발지와 목적지라는 고정된 의미가 존재할까? 아니다. 엣지 객체도 순서가 없는 쌍이다. 유방향 그래프에서를 생각해보면 정점 세트는 바뀌지 않지만 엣지 세트가 방향이 있는 세트로 바뀔 것이다. 만약 엣지 세트가 같다면 V2 -> V1로는 이동할 수 없다. 즉, { (V1, V2), (V2, V3), (V3, V4), (V4, V1), (V1, V3), (V2, V4)} 이다. 부분집합과 순서쌍의 차이인 것이다. 이것은 매우 중요하다. 웹을 생각해보자. 내가 어떤 웹 사이트를 들어갔는데 뒤로 돌아갈 수 없다면 다시 처음부터 찾아와야할 것이다. 얼마나 불편한가? 

 

그래프에 대해 자세히 알아보기

위와 같이 엣지 세트가 존재한다고 생각했을때, 특정 노드에서 다른 노드로 갈 수 있는지를 확인하기 위해서 걸리는 시간은 O(E)일 것이다. 이것은 공간도 O(E)를 요구하는 것에 비해서 할 수  있는 작업이 매우 제한적이다. 조금 변형을 해야 쓰기에 효율적일 것 같다. 

만약 이 엣지 리스트를 매트릭스 즉, 행렬로 바꾼다면 어떨까? 이것을 adjacency matrix, 인접 행렬이라고 부른다. 인접 행렬은 그래프에서 노드 사이에 간선이 포함된 표현이다. 일종의 look-up table이다. 값이 1이면 edge가 존재하고 0이면 없다고 생각했을때 원하는 노드에 edge가 존재하는지는 matrix[v1][v2] 이처럼 간단하게 확인할 수 있다. 이 행렬을 자세히 살펴보면 이 그래프의 특성을 알 수 있다. 행렬이 대칭이라면 무방향일 것이고 그렇지 않다면 유방향일 것이다. 

이렇게 행렬을 사용하면 내가 원하는 노드간 edge가 존재하는지 찾는데 O(1)의 시간이 걸린다. 근데 만약 노드의 갯수보다 엣지의 수가 적은 경우는 어떨까? 물론 O(1)의 시간이 걸리지만 인접 행렬의 문제점은 항상 O(V^2)의 공간이 필요하다는 점이다. 항상 이 경우가 옳다고 할 수 없다 .

이런 경우엔 인접 리스트라는 것이 있다. 인접 행렬과 엣지 리스트를 섞은 느낌이다. 하나의 정점에서 인접한 정점을 쉽게 볼 수 있게 해주는 배열이다. 이는 그래프에서 가장 널리 사용한다. 내가 원하는 경로가 연결되어 있는지를 알고 싶을때 전체 노드에 관한 정보를 담는 인접 행렬이 알맞을까? 공간 낭비가 될 수 있다. 이 경우 인접한 이웃만 알면된다. 인접 리스트는 배열이 있고 배열은 노드의 개수만큼 할당이 된다. 하나의 인덱스는 하나의 노드의 인접한 정보를 담기 위해서 존재하는 것이다. 여기에서 linked list가 구현이 된다. 해당 인덱스에 인접한 정보들이 하나씩 추가되는 것이다. 만약 이 리스트의 제일 처음에 내가 원하는 정보가 있다면 O(1)의 시간이 걸리지만 리스트 맨끝에 존재한다면 해당 노드의 인접 정보만큼의 시간이 걸리게 된다는 단점도 있다. 그렇다면 공간의 양은 배열을 위해 O(V)의 크기와 엣지의 갯수에 따라 달라지는 공간 O(E), 그래서 O(V+E)가 된다.

결국 인접 행렬, 인접 리스트 무엇을 사용해야할까? 상황에 맞게 내가 원하는 기능에 맞춰서 사용해야한다.

 

참조 - 참조된 링크엔 이미지가 있어 이해하기 더 용이합니다.

- https://medium.com/basecs/a-gentle-introduction-to-graph-theory-77969829ead8

A Gentle Introduction To Graph Theory

- https://medium.com/basecs/from-theory-to-practice-representing-graphs-cfd782c5be38

From Theory To Practice: Representing Graphs