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

그래프란?

그래프는 노드와 간선으로 구성된 자료구조입니다. 간선은 노드를 직접 연결하며 방향의 유무와 단방향, 양방향에 의해 다양한 종류로 나눌 수 있습니다.

그래프의 구현 방법

인접 행렬

• 2차원 배열을 사용하여 두 노드간의 관계를 0과 1로 표현하는 방식 (노드 간 직접 연결 되어있으면 1, 아니면 0)
• 인접 리스트에 비해 구현이 쉬우며 모든 노드들의 간선 정보가 있기 때문에 간선의 존재 여부를 확인할 때 O(1)의 시간복잡도를 가집니다.
• 무조건 2차원 배열이기 때문에 메모리가 낭비될 수 있습니다.

인접 리스트

• 각 노드마다 직접 연결된 모든 노드들의 리스트를 저장하는 방식
• 노드들의 연결 정보를  탐색할 때 O(n)의 시간복잡도를 가지며 메모리 사용량이 적습니다.
• 인접 행렬보다 구현이 어렵고 간선의 존재 여부를 확인하는데 O(E : 간선 개수)의 시간 복잡도를 가집니다.

그래프의 종류

유향 그래프

간선에 방향성이 있어 한 노드에서 다른 노드로만 이동할 수 있는 그래프입니다.

무향 그래프

간선에 방향이 없어 양쪽 방향으로 이동 가능한 그래프입니다.

가중치 그래프

간선에 가중치가 부여된 그래프입니다.

트리

순환이 없고 연결된 유향 비순환 그래프의 한 종류로, 계층적 구조를 나타내기 좋습니다.

그래프의 활용

BFS

너비 우선 탐색으로 시작 노드에서 가까운 노드부터 차례대로 탐색하는 방법입니다.

DFS

깊이 우선 탐색으로 시작 노드에서 하나를 선택하여 계속해서 더 이상 방문할 수 있는 정점이 없을 때까지 탐색하는 방법입니다.

최단 경로 알고리즘

다익스트라

벨만-포드

플로이드 워셜

최소 신장 트리 (MST)

위상 정렬