[코테 스터디] 그래프

그래프(Graph)

노드(Node)와 간선(Edge)을 이용한 비선형 데이터 구조

📎 비선형 데이터 구조?
선형 데이터 구조는 하나의 자료 뒤에 하나의 자료만 오도록 나열한 것입니다. (ex. 스택, 큐)
반면, 비선형 데이터 구조는 하나의 자료 뒤에 n개의 자료가 올 수 있습니다. (ex. 트리, 그래프)

그래프 용어

위 그림은 집에서 강남까지 가는 경로와 시간을 나타내는 그래프입니다.

• 노드: 각 장소들을 나타내는 동그라미
• 간선: 노드들을 잇는 화살표
• 가중치: 각 경로마다의 소요 시간을 나타내는 숫자

사용하는 이유

데이터 간의 관계를 표현

그래프 종류

	있음	없음
간선의 방향	방향 그래프	무방향 그래프
가중치	가중치 그래프
순환	순환 그래프	비순환 그래프

순환이란 특정 노드에서 시작해 간선을 따라 다시 돌아오는 경로가 있는 것 입니다.

1 → 2 → 3 → 1 로 다시 돌아올 수 있다.

그래프 구현

그래프의 구현 방식에는 인접 행렬과 인접 리스트가 있습니다.

인접 행렬

2차원 배열을 활용
배열의 인덱스는 노드, 값은 가중치로

graph[0][1] = 400; // 0 -> 1 간선의 가중치가 400

*빈 인덱스에는 -1이나 아주 큰 값을 넣는다

인접 리스트

노드를 정의 (정점 v, 가중치 w, 다음 노드 정보 next)
노드 개수만큼 배열을 준비
배열의 인덱스는 각 시작 노드를 의미하며 배열의 값에는 다음 노드를 연결

1 → 2 (가중치 3)
2 → 1 (가중치 6)
ㅤ→ 3 (가중치 5)
…

구현 방식 비교, 장단점

• 인접 행렬의 장점 ⇒ 간선 정보 확인의 시간 복잡도
• 인접 리스트의 장점 ⇒ 메모리

	메모리 사용	간선 정보 확인의 시간 복잡도
인접 행렬	O(N^2)	O(1)
인접 리스트	O(N + M)	O(N)
	*N = 노드 개수, M = 간선 개수