코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
자료구조 — 효율적인 데이터 관리의 핵심 → 트리와 그래프
무방향: 방향: 가중:
A --- B A → B A --5-- B
| | ↑ ↓ | |
C --- D C ← D 3 2
| |
C --4-- D
용어:
- 차수(Degree): 연결된 간선 수 (방향: 진입/진출 차수)
- 경로(Path): 정점 시퀀스 (모든 간선이 다름)
- 사이클(Cycle): 시작=끝인 경로
- 연결(Connected): 모든 정점 쌍 사이 경로 존재오늘은 그래프라는 자료구조를 배워보겠습니다.
그래프는 정점과 간선으로 이루어진 구조예요.
수학적으로 G = (V, E)로 표현하는데, V는 정점 집합, E는 간선 집합이에요.
왼쪽 그림을 보세요. 무방향 그래프에서는 A와 B 사이에 양방향 연결이 있어요.
이때 간선에 방향이 없으므로 A에서 B로, B에서 A로 모두 이동 가능합니다.
가운데 그림은 방향 그래프예요. 간선에 화살표가 있어서 A에서 B로만 갈 수 있죠.
방향 그래프에서는 A에서 B로 가는 것과 B에서 A로 가는 것이 다릅니다.
오른쪽의 가중 그래프를 보면, 간선마다 숫자가 적혀 있어요.
이 숫자를 가중치라고 하는데, 도로의 거리나 통신 비용을 나타낼 수 있어요.
하단의 용어 정리를 함께 보시죠.
정점은 노드라고도 부르고, 간선은 두 정점을 연결하는 선이에요.
차수는 한 정점에 연결된 간선의 수를 뜻합니다.
경로는 정점들을 간선으로 연속 연결한 것이고, 사이클은 시작점으로 돌아오는 경로예요.
그래프가 왜 이렇게 중요할까요?
소셜 네트워크에서 사용자가 정점, 친구 관계가 간선이에요.
내비게이션에서는 교차로가 정점, 도로가 간선, 거리가 가중치입니다.
웹 크롤링에서 페이지가 정점, 하이퍼링크가 간선이 되죠.
패키지 의존성에서는 모듈이 정점, import 관계가 방향 간선이에요.
이처럼 관계가 있는 데이터라면 거의 모두 그래프로 표현할 수 있어요.
배열이나 트리로는 표현하기 어려운 복잡한 관계를 그래프가 자연스럽게 담습니다.
자, 그럼 이 그래프를 컴퓨터에 어떻게 저장할지 알아볼까요?