그래프

그래프(Graph)란?

: 정점(=노드)과 간선으로 이루어진 구조

: 비선형 자료구조 - 하나의 자료 뒤에 여러개의 자료가 존재할 수 있음 !

 

 

 

 

그래프를 구현하는 방식

1. 인접 행렬

: |V| * |V| 크기의 2차원 배열을 만들어서 연결 관계를 표현하는 것. [ |V|는 정점 수 ]

• A→B로 가는 길이 있다면 배열의 값을 1로, 가는 길이 없다면 배열의 값을 0으로 지정한다.
• ‘플로이드-워셜’ 알고리즘에 사용
  

  

주요 시간 복잡도와 공간 복잡도

• 특정 정점 I, J가 연결되어 있는지 확인 : O(1)
• 특정 정점과 연결되어 있는 모든 정점을 확인: O(|V|)
• 공간 복잡도: O(|V|*|V|)

 

 

2. 인접 리스트

: |V| 개의 연결 리스트를 만들고, 연결 리스트에 특정 정점과 인접해있는 정점들의 정보를 담는 방식

• ‘다익스트라’ 알고리즘에 이용
  

  

주요 시간 복잡도와 공간 복잡도

• 특정 정점 I, J가 연결되어 있는지 확인 : O(min(degree(I)),degree(J))
• 특정 정점과 연결되어 있는 모든 정점을 확인: O(degree(X))
• 공간 복잡도: O(|V|+|E|)

 

 

 

 

 

 

REFERENCE

코드트리