그래프

정점과 간선들로 이루어진 집합
정점(vertex) ⇒ Node
간선(Edge) ⇒ 정점을 잇는 선

📌 특징

Indegree : 들어오는 간선

Outdegree : 정점으로 나가는 간선

가중치 : 정점과 정점 사이에 드는 비용

📌 컴퓨터에는 어떻게 알려줄까???

인접행렬 이용!!!
(정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬)

Ex)

a[3][5] = 1 //  3번노드 → 5번노드 (단방향 경로)
b[3][5] = 1
b[5][3] = 1 // 3번노드 -> 5번노드 (양방향 경로)

인접리스트로도 가능!!!

그래프가 희소할 때는 인접리스트, 조밀 할 때는 인접행렬이 좋다.

• 그래프가 희소할 때 (sparse)

간선이 없어서 인접행렬의 대부분의 요소가 0인데도 불구하고 해당 부 분을 포함해 2차원 배열을 만들어야 된다.

• 그래프가 조밀할 때 (dense)
  

메모리적 효율성은 동일해지고 정점i에서 정점j까지의 간선이 있는지 확인하는 속도가 더 빠르다.

• 공간복잡도
  

인접행렬 : O(V^2)
인접리스트 : O(V + E)

• 시간복잡도 (간선 한개 찾기)
  

인접행렬: O(1)
인접리스트: O(V)

• 시간복잡도 (모든 간선 찾기)
  

인접행렬: O(V^2)
인접리스트: O(V+E)