그래프(Graph)란?

그래프(Graph)란, 다음의 2가지 요소로 구성된 자료구조이다.

1. vertex(혹은 node)의 집합

2. vertex 쌍을 잇는 각 edge(간선)들의 모음

그래프에 V개의 vertex가 있을 때, 각 vertex는 0부터 V-1까지의 숫자로 이름 붙인다. 

각 vertex를 잇는 edge는 v-w 혹은 (v,w)와 같이 표현한다.

         

그래프는 단지 vertex들의 집합과 edge들의 모음일 뿐이라는 것을 기억한다면, 위의 두 그래프는 완전히 동일하다는 것을 알 수 있을 것이다.

그래프 개념은 실생활의 많은 곳에서 사용되는데, 지도, 웹 상의 링크, 전자회로, 스케줄링, 전자상거래, 매칭, 컴퓨터 네트워크, 소셜 네트워크 등에 폭넓게 적용된다. 적용 분야에 대한 자세한 내용은 여기를 참고하자.

---

그래프를 표현하는 방법에는 여러가지가 있을 수 있는데, 어떤 방식을 사용하든 다음의 사항들을 고려해야 할 것이다.

✔︎ 실제 응용 상황에서, 그래프 타입을 수용할 수 있는 적당한 공간(space)

✔︎ 그래프를 처리하는 데 있어 시간적으로 효율적(time-efficient)인 구현 방법

위의 사항들을 고려해서, 다음 3가지의 그래프 표현법에 대해 알아보자.

   1. 인접 행렬(adjacency matrix)

    •  V Graph(vertex가 V개인 그래프)라면, V x V의 boolean 배열을 사용하는 것이다. 만약 v와 w 모두를 잇는 edge가 존재한다면(단, undirected graph인 경우), 행렬에서 (v,w)와 (w,v) 모두 true가 되고, 반대의 경우 false가 된다.

    •  weighted graph(가중 그래프)를 표현할 때 사용되기도 한다. 만약 adj[i][j] = 3이라면, i에서 j로 가는 weight가 3인 edge가 존재한다는 뜻이다.

장점:  구현이 쉽다. edge를 제거하거나, 한 vertex에서 다른 vertex로 가는 edge가 존재하는지 알아내는 연산을 수행하는 데 O(1)의 시간이 걸린다. 

단점:  위의 고려사항 중 첫번째를 만족하지 못한다. 세상에는 vertex가 수백만 개인 그래프도 존재하는데 이 경우 행렬의 크기가 너무 커진다. 또한 edge가 많든 적든 무조건 V^2에 비례하는 공간이 필요하므로 비효율적이다. 즉 그래프가 sparse하든 dense하든 공간 복잡도 측면에서 언제나 좋지 못하다.

   2. edge들의 배열

    •  이를테면 한 쌍을 이루는 vertex들을 2개의 int로 표현해 Edge라는 클래스를 만들고, Edge들을 배열에 담는 방식이다.

    •  이 방법은 두번째 고려사항을 만족하지 못한다. 어떤 vertex와 인접한 vertex들을 구하려면 배열의 모든 요소들을 다 찾아봐야 하기 때문이다. 즉 시간 복잡도가 크다.

   3. 인접 리스트(adjacency list)의 배열

    •  각 vertex들을 index로 하는 배열을 만들고, 각 배열 안에는 해당 vertex와 인접한 vertex들을 List 형태로 넣어 놓는 방식이다. 아래 그림을 참고하자.

    •  이 방법은 대부분의 경우에 시간, 공간적인 요구사항을 모두 만족한다.

    •  단, 한 vertex에서 다른 vertex로 가는 edge가 존재하는지 알아내는 연산을 수행하는 데 O(V)의 시간이 걸리므로, 이 부분은 인접 행렬에 비해 느릴 수 있다.

    •  특히 sparse(not dense)한 그래프의 경우, 이 방법이 표준적인 자료구조라고 할 수 있다.

다음은 vertex와 edge의 개수, 각 edge들을 입력 받은 후, 각 vertex마다 인접한 vertex들을 출력하는 코드다. (geeksforgeeks를 참고함)

다음은 파일을 입력 받아 각 vertex마다 인접한 vertex들을 출력한다. (Algorithms by R. Sedgewick을 참고함)