자료구조 그래프 정리

자료구조는 내가 저장하려는 데이터를 효율적으로 저장하고 관리하는 방법이죠, 

어떻게 하면 적은 메모리를 사용해서 데이터를 저장하고 관리할 수 있을까?에 관한 것입니다.

자료구조의 선택은 실행 성능의 향상을 기대할 수 있게 합니다.

비선형 자료구조의 하나인 그래프에 대해 알아보겠습니다.

 

(1)트리와 그래프 차이

같은 비선형 자료구조의 트리 자료구조는 여러개의 노드가 있다면 부모에서 자식 관계로 이루어진 자료구조 였습니다. 

부모, 자식 관계로 이루어진 자료구조이며 단방향 그래프의 한 종류입니다.

a->b 이동은 가능하지만 b->a의 이동은 불가능합니다. 즉, 경로는 단 하나만 존재할 수 있습니다.

 

반면에 그래프는 노드가 있다면 트리처럼 단방향으로만 이루어지는게 아닌, a->b / b->a 모두 가능합니다.

어떤 방향으로든 이동할 수 있는 경로가 그래프입니다. 다양하게 이동할 수 있기 때문에 트리처럼

한쪽으로 이동하는 것과는 차이점을 보입니다.

a라는 노드에서 c라는 노드로 이동하면, 트리는 한쪽 방향으로만 이루어지기 때문에 단일 경로만 존재하지만

그래프는 a에서 b를 거치거나 a에서 c로 바로 갈 수도 있습니다.

그래서 트리는 경로가 하나이기 때문에 노드에 대한 정보만 저장해주면 되는데, 반면

그래프는 노드에서 노드로 이동하는 경로가 굉장히 많아서 노드 뿐만 아니라 간선의 정보까지 저장을 해줘야 합니다.

트리처럼 단방향이 아닌 여러 방향으로 이루어지기 때문에 노드, 간선의 정보 모두 저장해야 합니다.

 

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

 

그래프의 구성요소

• 정점(vertex) : 노드의 집합
• 간선(edge) : 정점 쌍의 집합
• ex. 구글 지도의 각 위치는 정점으로, 경로는 간선으로 표시한다

그래프의 종류에는 무방향 그래프, 방향그래프, 가중치 그래프(네트워크), 비가중치 그래프(가중치 값이 없는게 아닌 모두 1인 그래프입니다), 순환 그래프, 비순환 그래프(사이클 형성x)가 있습니다.

그래프의 구현 방식에는 정점의 개수 N이 있다면 N*N의 메모리에 할당해주는 2차원 배열 구현방식과 연결 리스트가 있습니다.

 

2차원 배열 구현

• 2차원 배열은 정점의 개수를 N * N 메모리에 할당해주며, 행은 출발지, 열은 도착지를 의미합니다.
• 4개의 정점이라면 4X4 = 16개의 메모리를 할당합니다.
• 가중치가 1인 비가중치 그래프입니다.
• 장점은 간선이 있는지 알아보거나 추가하거나 제거하는 것이 바로 가능하기 때문에 O(1)의 시간이 걸려 속도가 빠릅니다.
• 단점은 간선이 희소 그래프인 경우(간선이 거의 없는 경우) 메모리가 낭비 됩니다.

인접 리스트로 구현

• 낭비되는 메모리가 발생하는 2차원 배열 구조를 보완하기 위해 사용합니다. 
• 정점을 배열에 저장합니다. 정점이 4개라면 4개의 배열을 만들고 정점마다 갈 수 있는 곳들을 연결리스트로 연결합니다.