[자료구조]Graph 공부: 그래프의 종류, 인접행렬과 인접리스트

트리 vs 그래프 

 

 Tree 자료구조는 계층적 데이터를 표현하는 좋은 방법이지만, 하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에 원형 또는 순환적인 종속성을 표현할 수 없습니다. 

 

 Graph 자료구조는 원형 속성을 사용하여 다양한 경로를 표현할 수 있습니다. 

 

 

그래프의 종류

 

 그래프는 노드(vertex) 데이터뿐만 아니라 노드 사이의 에지 데이터도 저장해야 합니다. 

 

G = (V, E) 

V = vertex, 노드

E = vetex의 쌍으로 표현됨(일대일 관계)

 

• 비가중 그래프(unweighted graph)

 비가중 그래프는 각 노드에 다른 어떤 노드들이 연결되어 있는지에 대한 정보를 가지며 에지에 가중치를 부여하지 않습니다. 

 즉, 모든 에지가 동일한 값을 갖습니다.

 

 

• 가중 그래프(weighted graph)

 가중 그래프는 에지에 가중치(weight) 또는 더 많은 정보를 부여할 수 있습니다. 

 

 

• 무방향 그래프(undirected graph)

 그래프는 방향성이 있는 그래프와 없는 그래프로 구분할 수 있습니다. 

 

 무방향 그래프는 에지가 양방향임을 의미합니다. 

 

 

• 방향 그래프(directed graph)

 방향 그래프는 방향이 있는 그래프 입니다. 

 

 예를 들어 어떤 도로 A, B에서 A와 B사이의 길이 일방 통행으로  제한되어 있다면 방향 그래프로 나타내야합니다. 

 

 방향 그래프로 A, B 양쪽으로의 길을 모두 만들기 위해선 A->B, B->A 총 두 개의 에지를 만들어야 합니다. 

 

 

• 완전 그래프(complete graph)

 완전 그래프는 n개의 vertex들이 모두 서로 연결된 그래프입니다. 

 

 즉, 하나의 vertex가 n-1개의 나머지 vertex들과 연결되어 있습니다. 

 

 무방향 그래프의 경우 에지의 개수는 n(n-1)/2개 이며, 방향 그래프의 경우 n(n-1)개의 에지를 가집니다. 

 

 

• 밀집 그래프(dense graph)

 밀집 그래프는 n개의 vertex들이 대부분 서로 연결된 그래프입니다. 

 

 에지의 개수는 무방향, 방향 그래프 모두 O(n^2)개를 가집니다. 

 

 

• 희소 그래프(sparse graph)

희소 그래프는 각 vertex들이 상수 개의 vertex와 연결된 그래프입니다. 

 

즉, 모든 vertex들이 연결된 vertex의 수가 동일합니다. O(1)

 

 에지의 개수는 O(n)개 입니다. 

 

 

 

 

그래프 표현하기

 

1. 인접 행렬로 그래프 표현하기 

 

 노드가 N개 있을 경우, 이 그래프는 NxN 크기의 2차원 배열로 표현할 수 있습니다. 

 

 이것을 인접 행렬(adjacency matrix)라고 합니다. 

 

 노드 i와 노드 j가 인접(연결)되어 있다면 인접 행렬 arr[i][j] = 1, arr[j][i] = 1로 set 하여 연결되어있음을 표시합니다. (무방향 그래프의 경우)

 

 연결되어 있지 않다면 arr[i][j] = 0 이겠지요?

 

 

 

2. 인접 리스트로 그래프 표현하기 

 

 행렬을 이용하여 그래프를 표현할 때의 가장 큰 문제점은 노드 개수의 제곱에 비례하는 메모리를 사용한다는 점입니다. 

 

 즉, 두 노드가 서로 연결되어 있지 않더라도 모든 노드 사이의 에지 정보를 저장해야 합니다. 

 

 이러한 방식 대신 각 노드에 직접 연결되어 있는 노드의 ID만을 저장하는 방식으로 그래프를 표현할 수 있는데 이러한 방식을 인접 리스트(adjacency list)라고 합니다. 

 

 N개의 연결 리스트 adjList[N]을 선언하여, adjList[i]는 노드 i로부터 시작하는 에지에 연결된 노드들을 연결하는 연결 리스트의 시작을 나타냅니다.