[자료구조]Graph(그래프)구현

1. 그래프 구현- 인접행렬(Adjacency Matrix)

1) 개념

인접 행렬은 노드의 개수가 N일때, \(N \times N\) 행렬로 표현된다. 연결된 노드끼리는 행렬의 성분을 1로, 단절된 부분은 0으로 채워 넣는다.

따라서 인접 행렬은 이차원 배열을 이용하는 방식이다.

특징

• 노드의 개수가 N인 그래프를 인접 행렬로 표현
  1. 간선의 수와 무관하게 항상 \(N^2\)개의 메모리 공간이 필요하다.
• 무방향 그래프를 인접 행렬로 표현한다면 이 행렬은 대칭(Symmetric Matrix)가 된다.
  1. 물론 방향 그래프는 대칭 행렬이 안 될 수 있다.
• 인접 리스트를 사용한 그래프 알고리즘들(Ex. 너비 우선 탐색)또한 인접 행렬에서도 사용이 가능하다.

2) Pseudo Code

if(노드 i,j를 잇는 간선이 그래프에 존재): 
	M[i][j] = 1;

else:
	M[i][j] = 0;

3) Python 구현

graph = [
    [0, 1, 1, 0], 
    [1, 0, 1, 1], 
    [1, 1, 0, 0], 
    [0, 1, 0, 0]
]

2. 인접 리스트(Adjacency List)

1) 개념

연결리스트로 표현해서, 각 노드에 인접하게 연결되어 있는 노드들을 순서에 상관없이 이어준다. 인접 행렬보다 빠르다. 하지만 구현이 복잡하다.

인접 리스트(Adjacency List)로 그래프를 표현하는 것이 가장 일반적인 방법 이다.

• 모든 정점(혹은 노드)을 인접 리스트에 저장한다. 즉, 각각의 정점에 인접한 정점들을 리스트로 표시한 것이다.
  1. 배열(혹은 해시테이블)과 배열의 각 인덱스마다 존재하는 또 다른 리스트(배열, 동적 가변 크기 배열(ArrayList), 연결리스트(LinkedList) 등)를 이용해서 인접 리스트를 표현
  2. 정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 리스트에 쉽게 접근할 수 있다.
• 무방향 그래프(Undirected Graph)에서 (a, b) 간선은 두 번 저장된다.
  1. 한 번은 a 정점에 인접한 간선을 저장하고 다른 한 번은 b에 인접한 간선을 저장한다.
  2. 정점의 수: N, 간선의 수: E인 무방향 그래프의 경우
     • N개의 리스트, N개의 배열, 2E개의 노드가 필요
• 트리에선 특정 노드 하나(루트 노드)에서 다른 모든 노드로 접근이 가능 -> Tree 클래스 불필요
  1. 그래프에선 특정 노드에서 다른 모든 노드로 접근이 가능하지는 않음 -> Graph 클래스 필요

2) Pyhton 구현

graph = [[] for _ in range(4)]

# 노드 A
graph[0].append('B')
graph[0].append('C')

# 노드 B
graph[1].append('A')

...

graph = [['B', 'C'], ['A', 'C', 'D'], ['A', 'B'], ['B']]

3. 인접 행렬 VS 인접 리스트

• 인접 행렬 ➜ 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우 사용
  • Pros
    1. 두 노드의 간선의 존재 여부를 바로 알 수 있음 ((M[i,j]를 O(1) 안에 즉시 알 수있다.)
    2. 정점의 차수는 \(O(N)\)안에 알 수 있다. ➜ 인접 배열의 i번째 행 또는 열을 모두 더한다.
  • Cons
    1. 모든 관계를 기록함으로 노드의 개수가 많을 수록 불필요한 메모리 낭비가 일어남
    2. 즉, 어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 순회해야함.
    3. 그래프에 존재하는 모든 간선의 수는 \(O(n^2)\)이다. ➜ 인접 행렬 전체를 조사한다.
• 인접 리스트 ➜ 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우
  • Pros
    1. 연결된 것들만 기록함
    2. 어떤 노드의 인접한 노드들을 바로 알 수 있다.
    3. 그래프에 존재하는 모든 간선의 수는 O(N+E) 안에 알 수 있다. ➜ 인접 리스트 전체를 조사한다.
  • Cons
    1. 두 노드가 연결되어 있는지 확인이 인접 행렬보다 느림
    2. 간선의 존재 여부와 정점의 차수: 정점 i의 리스트에 있는 노드의 수 즉, 정점 차수만큼의 시간이 필요

4. 그래프의 탐색

1) 깊이 우선 탐색(Depth-First Search, DFS)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
• 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
  • 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다.

2) 너비 우선 탐색(Breadth-First Search, BFS)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
• 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
  • Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
  • 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
  • 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색

Reference

[Python] 그래프 (인접 행렬, 인접 리스트) + DFS/BFS를 배우기 앞서 알아야 할 개념들 (탐색 알고리즘, 자료구조)
[자료구조]그래프
[자료구조] 그래프(Graph)란

DataStructure 카테고리 내 다른 글 보러가기