💻 [코테06] 11장 그래프

11장. 그래프

11-1. 그래프의 개념

• 노드와 간선을 이용한 비선형 데이터 구조
• 보통 데이터 간의 관계를 표현하는데 사용
• 데이터를 노드로, 노드 간의 관계나 흐름을 간선으로 표현
• 간선은 방향이 있는 경우, 없는 경우 모두 가능
• 관계나 흐름에서 정도를 표현할 필요가 있다면 가중치 추가하여 표현

1) 그래프의 특징과 종류

• 흐름을 표현하는 방향성(방향 그래프, 무방향 그래프)
• 흐름의 정도를 표현하는 가중치(가중치 그래프)
• 시작과 끝의 연결 여부를 보는 순환(순환 그래프, 비순환 그래프)

2) 그래프 구현

• 인접 행렬을 통한 그래프 구현
  • 인접 행렬은 배열을 활용하여 구현
  • 노드 : 배열의 인덱스
  • 가중치 : 배열의 값
  • 출발 노드 : 인덱스의 세로 방향
  • 도착 노드 : 인덱스의 가로 방향
• 인접 리스트를 통한 그래프 구현