그래프

• 무방향 그래프 == 양방향 그래프 : 방향이 없다
• 방향 그래프 : 방향이 있다
• 순환하는 그래프
• 한방향으로만 전달되는 그래프
• 비순환 그래프(DAG)

그래프를 코드로 표현하는 방법

1. 인접행렬

   

   • 위의 표는 방향 그래프

     

   • 위의 표는 무방향 그래프(대칭 구조)

2. 인접리스트

   

   • 위의 표는 방향 그래프

     

   • 위의 표는 무방향 그래프

인접행렬 vs 인접리스트

• 인접행렬은 무조껀 노드가 N개면 n ** 2만큼 메모리를 쓴다
• 인접행렬은 공간이 큰만큼 속도가 빠르다
• 인접리스트는 간선개수가 적으면 적을수록 메모리를 적게 쓴다