Graph

[CS][Data Structure] 그래프 (Graph)

그래프란? 그래프는 노드와 간선으로 구성된 자료구조입니다. 간선은 노드를 직접 연결하며 방향의 유무와 단방향, 양방향에 의해 다양한 종류로 나눌 수 있습니다. 그래프의 구현 방법 인접 행렬 2차원 배열을 사용하여 두 노드간의 관계를 0과 1로 표현하는 방식 (노드 간 직접 연결 되어있으면 1, 아니면 0) 인접 리스트에 비해 구현이 쉬우며 모든 노드들의 간선 정보가 있기 때문에 간선의 존재 여부를 확인할 때 O(1)의 시간복잡도를 가집니다. 무조건 2차원 배열이기 때문에 메모리가 낭비될 수 있습니다. 인접 리스트 각 노드마다 직접 연결된 모든 노드들의 리스트를 저장하는 방식 노드들의 연결 정보를 탐색할 때 O(n)의 시간복잡도를 가지며 메모리 사용량이 적습니다. 인접 행렬보다 구현이 어렵고 간선의 존재 ..