자료구조 그래프(Graph) 구현방법

자료구조 그래프의 구현방법

 

그래프의 추상 자료형

• 그래프 생성 - n 개의 노드를 가지는 빈 그래프를 만든다.
• 그래프 삭제 - 그래프 G의 모든 노드 V와 간선 E를 제거한후, 그래프를 제거한다.
• 간선 추가 - 그래프 G에 노드 u 와 노드 v를 연결하는 간선 e를 추가한다.
• 간선 제거 - 그래프 G의 간선 (u,v) 또는 (v,u)를 제거한다.

방향 그래프(Directed Graph) 라면 u->v 와 v->u는 서로 다른 간선이다.

 

그래프 구현 방법

1. 인접 행렬 (Adjacency matrix)

• 2차원 배열 (aka 행렬) 을 이용
• 두 개의 노드가 간선으로 연결되어 있다면 인접하다.
• 인접 행렬에 그래프의 간선 정보를 저장한다.
• 간선의 존재 유무
  • 간선 (i, j) 가 존재: [i][j] = 1
  • 간선 (i, j) 가 존재하지 않는다: [i][j] = 0

인접 행렬에 간선 정보를 저장

 

인접 행렬의 장점

1. 두 노드의 간선 정보를 확인하는것이 빠르다. O(1)
2. 새로운 간선을 추가하고 제거하는것이 빠르다. O(1)

인접 행렬의 문제점

1. 간선의 개수와 상관없이 배열의 크기는 항상 N * N 개이다. (N은 노드의 개수)
   • 위 그래프에서 노드가 4개이기 때문에 배열의 원소 개수는 (4 x 4) = 24 개
   • O(N^2) 의 메모리를 사용
2. 특정한 노드에 인접한 노드를 찾기위해서 모든 노드를 순회해야 한다.
3. 노드를 추가 하거나 제거하는데 오래 걸린다. O(N^2)
4. 그래프의 모든 간선의 수를 찾는데 O(N^2)

인접 행렬은 상대적으로 노드의 개수가 적고 간선의 수가 많을때 사용하는것이 좋다고 할 수 있다.

따라서 간선이 많은 밀집 그래프(Dense Graph)에 적합하다.

 

2. 인접 리스트 (Adjacency List)

• 인접 정보를 저장하는 리스트
• 연결 리스트의 1차원 배열이다.
  • 시작 노드를 기준으로 노드의 개수만큼 연결 리스트가 1차원 배열에 저장된다.
• 배열의 크기는 노드의 개수와 같다.

인접 리스트에 간선 정보 저장

인접 리스트의 장점

1. 메모리 효율이 좋다.
   • 메모리 사용량은 노드 수가 아닌 간선 수에 따라 달라진다.
2. 특정 노드에 직접 접근할 수 있어 인접한 노드를 찾기 쉽다.
3. 노드의 추가 삭제가 빠르다.
4. 새로운 간선을 빠르게 추가 할 수 있다. O(1)
5. 그래프의 모든 간선의 수를 찾는데 O(N+E)

인접 리스트의 문제점

1. 두 노드의 간선 정보를 확인하는데 오래걸린다.

인접 리스트는 노드의 개수가 많고 간선의 개수가 상대적으로 적을때 사용하는것이 좋다.

따라서 간선이 적은 희소 그래프(Sparse Graph)에 적합하다.

 

 

구현

GitHub