목차

학습목표

✔️ 그래프의 기본 개념 이해

✔️ 그래프의 종류 구분

✔️ 그래프 탐색 방법의 이해와 구현

✔️ 인접 행렬과 인접 리스트를 이용한 그래프 구현

그래프 (Graph)

✔️ 정점과 간선으로 이루어진 자료구조 (Cyclic)

• 연결된 정점간의 관계를 표현할 수 있는 자료구조

✔️ 그래프의 용도

• 지하철 노선도, 통신 네트워크, …

그래프 구조

✔️ 정점(Vertex): 각 노드

✔️ 간선(Edge): 노드와 노드를 연결하는 선 (link, branch)

✔️ 인접 정점(Adjacent vertex): 간선 하나를 두고 바로 연결된 정점

✔️ 정점의 차수(Dgree):

• 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • A, B의 차수는 2
  • C, D의 차수는 3
• 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배
  • 간선이 5개 → 모든 정점 차수의 합 10

✔️ 진입 차수(In-degree): 방향 그래프에서 외부에서 오는 간선의 수

✔️ 진출 차수(Out-degree): 방향 그래프에서 외부로 나가는 간선의 수

✔️ 경로 길이(Path length): 경로를 구성하는데 사용된 간선의 수

✔️ 단순 경로(Simple path): 경로 중에서 반복되는 정점이 없는 수

✔️ 사이클(Cycle): 단순 경로의 시작 정점과 끝 정점이 동일한 경우

그래프의 특징과 트리와의 차이