그래프

그래프 (Graph)

• 사물을 정점(Vertex)과 간선(Edge)로 나타내는 구조

종류

E : Edge (간선)
V : Vertex (정점)

무방향 비가중치 그래프

• 모든 노드의 연결여부를 확인하여야한다.
• 2차원 Matrix를 이용하여 확인하므로 O(V^2)이 소요되고, 값은 바로 확인할 수 있기 때문에 O(1)이 소요된다.

  인접 행렬(Adjacency Matrix)을 이용한 구현

방향 가중치 그래프

• 모든 간선이 방향을 가지고, 가중치를 가진 그래프
• 연결된 간선의 정보만 저장하기 때문에 공간은 O(E)가 소요되고, 노드만 확인하여 값을 확인하므로 O(V)가 소요된다.

  인접 리스트(Adjacency List)를 이용한 구현