Graph, 그래프 , 자료구조 [CPP]

[CS Interview] - 비선형 자료구조를 사용하는 이유

 

우리는 선형구조만으로 모든 것을 표현하지 못한다.

그래서 Tree를 그려내었고

Tree는 하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에

순환 또는 원형의 종속성을 표현할 수 없다.

때문에 우리는 또 다른 자료구조인 Graph를 구현하고자 한다.

 

즉, 노드 간의 더 자세한 경로의 표현을 하고싶다면

Tree 보다는 Graph가 더 적합한 자료구조라고 할 수 있다.

 

---

 

Graph는 우선 노드에 대한 데이터를 가지고 있을 뿐만 아니라 노드 간의 간선 데이터도 가지고 있어야 한다.

즉, 해당 노드의 값과 해당 노드와 연결된 노드에 대한 정보를 가지고 있어야 한다는 것이다.

 

edge, 간선은 무방향, 일방향 이 존재하고 해당 edge에 가중치가 있거나 없을 수 있다.

** 무방향은 곧 쌍방향을 의미한다. 방향이 구분이 없다는 얘기다.

 

일반적으로 최소 경로를 찾을 때

노드를 잇는 간선은 해당 노드와의 거리를 가중치로 잡는 경우가 많다.

 

 

해당 그래프는 특정 노드에서 다른 노드로 가는 여러가지 경로가 나올 수 있기 때문에

각 노드는 id와 같은 다른 노드와 구별되는 고유한 것이 있어야 한다.

 

 

---

 

C++에서는 그래프를 STL container를 이용하여 표현할 수 있다.

 

1. 인접 행렬로 표현

 

일반적으로 2차원 배열, N개의 노드는 N*N 행렬로 표현할 수 있다.

이 배열에서 가중치는 원소의 값이다.

가중치가 없다면 일반적으로 1,0만 원소로 가지게 한다면 1은 연결, 0은 연결되어있지 않음을 의미한다.

또는 -1로 연결되어있지 않음을 표현하기도 한다.

 

 

 

edge가 그렇게 많지 않은 이상

Node가 많아질수록 해당 Matrix는 Sparse한 행렬이 될 것이며

메모리 낭비가 되는 경향이 생긴다.

 

때문에 다른 방법을 찾았다.

 

2. 인접 리스트로 표현

 

연결 리스트를 이용하여 표현하는 것이다.

 

 

 

여기선 Edge의 개수에 비례하여 연결리스트가 표현된 것을 알 수 있다.

 

 

---

 

실제로 코딩테스트에서 이용할 땐

그래프는 배열로 많이 쓰인다.

배열은 임의 접근이 가능하기 때문이기도 하며

실제로 시간복잡도면에서 유리하기 때문이라고 보면 된다.