[Data Structure] Graph - 그래프

그래프는 자료의 관계도에 주로 사용되는 자료구조이다. 가장 대표적인 예는 역시 싸이월드 페이스북 친구이다.

나와 친구의 관계를 가중치1이라고 한다면, 친구의 친구는 가중치2 정도로 두고, 친구의 친구의 친구는 가중치3정도로 두는 것이다.

 

그러면 나를 기준으로 가중치가 1인 사람은 가장 가까운 사람들이고, 가중치가 2인 사람들은 그 다음으로 가까운 사람들이고, 3정도의 가중치는 내 친구와 그 사람의 친구가 서로 친구인 경우니까 그냥 남이다.

 

Graph

그래프는 이전의 링크드리스트에서 보던 노드라는 개념을 가져와서 사용한다. 다른 점이 있다면, 실제로 그래프에서는 노드 대신 Vertex ( 점 ) 와 Edge ( 간선 ) 을 사용한다. ( 참고로 vertex의 복수형은 vertices 이다 )

 

그래프에는 방향 그래프와 무향 그래프 ( 무방향 그래프 ) 가 있다. 또, vertices와 edges를 통해 나타내는 그래프에서 데이터의 삽입, 삭제, 탐색에는 linkedList와 matrix를 비교하여 이야기할 수 있다.

 

Directed graph ( 방향 그래프 )

방향그래프는 말 그대로 하나의 점 ( vertex ) 로부터 출발하여 다른 점으로 도착하는 하나의 방향을 가지는 그래프이다.

예를 들어, 위 그림에서 vertex 1 은 vertex 2, 3 으로 화살표를 내보내고, 4로부터 화살표를 받고 있다.

이걸 조금 더 정확하게 표현하면,

• vertex 1의 indegree는 1이고, outdegree는 2이다.
• vertex 2의 indegree는 2이고, outdegree는 1이다.
• vertex 3의 indegree는 2이고, outdegree는 1이다.
• vertex 1의 indegree는 1이고, outdegree는 2이다.

여기서 indegree는 받은 화살표의 개수이고, outdegree는 현재의 vertex 로부터 출발한 화살표의 개수이다.

 

그렇다면 5개의 노드가 있는 방향그래프에서 그릴 수 있는 edge ( 간선 ) 의 최대 개수는 몇일까?

 

undirected graph ( 무향 그래프, 무방향 그래프 )

무향그래프는 사실 양방향 그래프이다. 하지만, 방향 그래프와는 다르게, 양방향이어도 하나의 간선으로 헤아리는 게 차이점이다.

 

방향, 무향 그래프에 대해 설명했으니 이번에는 새로운 노드의 삽입, 삭제, 그리고 전체 그래프에 대한 탐색을 해보도록 하자.

 

 

우선 탐색먼저 보자.

모든 노드와 간선에 대해, 하나의 노드가 표현할 수 있는 방식은 두가지로 나뉜다.

1. 인접 리스트
2. 인접 행렬

인접 리스트는 말 그대로 하나의 노드에서 연결된 다른 노드를 표기하는 방법이고,

인접 행렬은 모든 노드에 대해 서로의 연결 상태를 매트릭스로 나타내는 방법이다.

 

위의 무향그래프를 예로 한 번 작성해보자.

먼저, 인접 리스트이다.

const nodes = {
  1: [2, 4],
  2: [1, 3],
  3: [2, 4],
  4: [1, 3]
}
/*
탐색: vertex 1, edges 2
탐색: vertex 2, edges 2
탐색: vertex 3, edges 2
탐색: vertex 4, edges 2
*/

인접리스트에서 우리가 원하는 결과를 탐색하기 위해서는 worst case로 모든 노드와 간선을 각각 ( 따로 ) 탐색해야한다.

점을 추가할 때: O(1)

점을 제거할 때: O(V + E)

간선을 추가할 때: O(1)

간선을 제거할 때: O(E)

공간복잡도: O(V + E)

 

 

다음은 인접 매트릭스이다.

const matrix = [
// 1  2  3  4
  [0, 1, 0, 1], // 1
  [1, 0, 1, 0], // 2
  [0, 1, 0, 1], // 3
  [1, 0, 1, 0], // 4
];

 

인접 매트릭스에서는 미리 모든 노드에 대해 정리해두었기 때문에 별도의 탐색없이 간선을 추가/제거할 수 있다. 대신, 새로운 노드를 추가하거나 제거할 때마다 새로운 매트릭스를 생성해야 하므로 제법 번거로운 작업을 한다. 하지만 데이터의 크기가 고정적이고 변하지 않는 경우에는 인접리스트에 비해 월등히 좋은 퍼포먼스를 낸다.

 

점을 추가할 때: O(V^2)

점을 제거할 때: O(V^2)

간선을 추가할 때: O(1)

간선을 제거할 때: O(1)

공간복잡도: O(V^2)

 

인접리스트는 Node의 추가, 삭제가 빈번하게 발생하거나 간선의 수가 V^2에 비해 훨씬 적은 그래프 ( 희소 그래프 ) 에,

인접행렬은 Edge의 추가, 삭제가 빈번하게 발생하거나 간선의 수가 V^2에 비례하는 그래프 ( 밀접 그래프 ) 에 적합하다.