Data structures (with python) - 2. Graph - 2.4. Graph Representation

Data structures (with python) - 2. Graph - 2.4. Graph Representation

 

💡 A graph can either be represented as an adjacency matrix or an adjacency list.

The adjacency matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j.

Adjacency list is an array of vectors. Size of the array is equal to the number of vertices. Let the array be array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs.

 

그래프는 인접성 행렬 또는 인접성 list으로 표현할 수 있습니다.

인접 행렬은 V x V 크기의 2D 배열로, 여기서 V는 그래프의 정점 수입니다. 2D 배열을 adj[][]라고 할 때, 슬롯 adj[i][j] = 1은 정점 i에서 정점 j까지 에지가 있음을 나타냅니다.

인접성 list는 벡터의 배열입니다. 배열의 크기는 정점의 수와 같습니다. 배열을 array[]라고 합니다. 항목 array[i]는 째 정점에 인접한 정점의 list을 나타냅니다. 이 표현은 가중 그래프를 표현하는 데에도 사용할 수 있습니다. 가장자리의 가중치는 쌍의 list으로 나타낼 수 있습니다.

 

 

Graph Representation

그래프를 표현하는 방법에는 크게 2가지 가 있다.

1. adjacency matrix

2. adjacency list

 

1. 인접행렬 (Adjacency matrix)는 그래프의 node들이 서로 어떻게 연결 되어 있는지를 이차원 array 로 표현 한 것

  - 행과 열이 각각 그래프의 노드를 나타내며, 노드 i 와 노드 j가 연결되어 있다면 matrix[i][j] (그리고 무방향 그래프의 경우 matrix[j][i]) 위치에는 1을, 연결되어 있지 않다면 0을 넣는다.

  - 인접 행렬은 그래프의 모든 노드에 대해 연결 정보를 저장하므로 메모리 사용이 많지만, 두 노드 간의 연결 여부를 바로 확인할 수 있는 장점이 있다.

 

파이썬에서 adjacency matrix는 2차원 list를 사용해 구현 가능하다.

 

matrix = [[0, 1, 1, 0, 0],  # 노드 0은 노드 1, 2와 연결
          [1, 0, 1, 1, 1],  # 노드 1은 노드 0, 2, 3, 4와 연결
          [1, 1, 0, 0, 1],  # 노드 2는 노드 0, 1, 4와 연결
          [0, 1, 0, 0, 1],  # 노드 3은 노드 1, 4와 연결
          [0, 1, 1, 1, 0]]  # 노드 4는 노드 1, 2, 3과 연결

2-2 undirected graph의 예시였던  5개의 노드를 가진 무방향 그래프(undirected graph)를 인접 행렬로 표현한 예시.

 

2. 인접리스트 (Adjacency List)는 그래프의 각 노드에 연결된 노드를 리스트로 표현한 것.

  - 인접 리스트는 각 노드의 리스트를 저장합니다.

  - 인접 리스트는 인접 행렬에 비해 메모리 사용이 적지만, 두 노드 간의 연결 여부를 확인하기 위해 리스트를 탐색해야 하는 단점이 있다.

 

파이썬에서 구현은 list 의 list로 구현 가능하다.

list = [[1, 2],     # 노드 0은 노드 1, 2와 연결
        [0, 2, 3, 4],  # 노드 1은 노드 0, 2, 3, 4와 연결
        [0, 1, 4],  # 노드 2는 노드 0, 1, 4와 연결
        [1, 4],     # 노드 3은 노드 1, 4와 연결
        [1, 2, 3]]  # 노드 4는 노드 1, 2, 3과 연결

왜 list의 list라고 말했냐면, array 의 형태라기보다 노드의 연결을 표현한 list 들의 list 이기 떄문.

 

그렇다면 

adjacency matrix 와 adjacency list의 차이점은 무엇일까?

 

1. 메모리 사용량

  - 인접 행렬은 그래프의 모든 노드 간의 연결 관계를 저장하므로 메모리 사용량이 많다.

노드의 수가 n 일 때, 인접 행렬은 n^2 의 공간을 차지한다.

  - 인접 list는 노드의 연결 리스트를 탐색해야 하므로 두 노드의 연결 여부를 확인하는 데에 더 많은 시간이 소요된다.

  최악의 경우 O(n)의 시간 복잡도를 가진다.

 

※O(n) 은 big-O 표기법으로 점근적 분석으로 알고리즘의 수행 시간을 분석할떄 사용하는 방법 추후 다룬다.

 

2. 연산 속도:

  - 인접 행렬은 두 노드 간의 연결 여부를 바로 조회할 수 있으므로 이 작업의 속도가 빠르다.
즉 노드 A와 노드 B가 연결되어 있는지 확인하는 작업은 O(1)의 시간 복잡도를 가진다.

  - 인접 리스트는 노드 연결 리스트를 탐새해야 하므로 두 노드의 연결 여부를 확인하는 데 더 많은 시간이 소요된다.

 최악의 경우 O(n)의 시간 복잡도를 가진다.

 

3. 그래프의 종류

  - 인접 행렬은 주로 완전 그래프에서 사용되며, 인접 리스트는 최소 그래프에서 주로 사용된다.

완전 그래프 : 모든 노드가 서로 연결되어 있는 그래프,

최소 그래프 : 대부분의 노드가 서로 연결되어 있지 않은 그래프.

 

인접 행렬과 인접 리스트의 정의와 형태를 보면 자연스레 이해갈 것이다.

 

appendix

좀 더 깊은 활용의 예를 들자면,

 

1. 인접행렬 :

 - 플로이드-워셜 알고리즘(Floyd-Warshall) : 모든 노드 쌍의 최단 경로를 찾는 알고리즘

 -  그래프가 작고 노드 간의 연결 여부를 자주 확인해야 하는 겨우 인접 행렬을 사용

 

2. 인접 리스트:

  - 다익스트라 알고리즘(Dikstra's Algoritm), 벨만-포드 알고리즘(Bellman-Ford) 같은 최단 경로 문제를 해결하는 알고리즘

  - 깊이 우선 탐색(DFS), 넓이 우선 탐색(BFS) 같은 그래프 탐색 알고리즘에서도 효과적.