[자료구조/알고리즘] 211008 자료구조 Graph 기초개념 복습

📌 Graph

스택과 큐와 달리 개념이 한번에 와닿지 않는게 바로 Graph 와 Tree 이다. BST는 개념도 이해가 잘 안된다..ㅎㅎ 기본적으로 생각하는 x , y축 그래프의 모양새가 아니라 복잡한 네트워크 망의 모양새이다.

☑ 그래프 실사용 예제

• 포털 사이트의 검색 엔진
• SNS에서 사람들과의 관계
• 네비게이션 (길찾기) 등에서 사용하는 자료구조

직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있고, 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다. 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge) 이라고 표현한다.

• 가중치 그래프 : 서울 부산 간선으로 연결되어있다/연결되어 있지 않다 정도만 나타내는 그래프
• 비가중치 그래프 : 서울에서 대전까지는 140km 떨어져있다.

☑ 인접행렬

두 정점을 바로 이어 주는 간선이 있다면 이 두 정점은 인접하다고 표현한다. 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬으로 2차원 배열의 형태로 나타낸다. 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한다.

❗ 인접행렬 예시

• 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이.
  예를 들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0 번째 줄의 1 번째 열에 어떤 값이 저장되어있는지 바로 확인가능.
• 가장 빠른 경로(shortest path)를 찾기.

☑ 인접리스트

인접 리스트는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현.

❗ 인접 리스트는 언제 사용할까?
메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용.
(인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지)