[기말고사] 6-2. 인접 메트릭스 vs. 인접 리스트

그래프 알고리즘 내용

• 그래프 데이터 구조
  • 종류
  • 매트릭스
  • 인접 리스트
• 그래프 탐색
  • BFS 및 응용
  • DFS 및 응용
• 탐욕적 그래프 알고리즘
• DP 그래프 알고리즘

인접 메트릭스

1) 그래프가 directed일 때, 

2) 그래프가 undirected일 때,

• undirected 그래프의 경우, 각 노드 사이에 연결이 있으면 두 번의 표기만으로 충분함
• 즉, (i, j)와 (j, i) 요소를 모두 채워넣을 필요가 없음
• 그러므로 sparse(희소)하다

인접 리스트

1) 그래프가 directed일 때, 

2) 그래프가 undirected일 때,

 

인접리스트 코드는 chatting paper에 그냥 적어둘 것!

(수업 시간 언급을 거의 안 했기 정리는 안 할래... 그러나 혹시 모르니까)

 

인접 메트릭스 vs. 인접 리스트

인접 메트릭스 O(n^2)		인접 리스트 O(m+n)
Win (상수 시간 소요)	1) (x, y)가 존재한다면, 누가 더 빨라?	Lose (O(m) // 간선의 수에 비례)
Lose (O(n) // 해당 노드의 수 행/열 확인)	2) 특정 노드의 차수 ( = 해당 노드에 연결된 간선의 수 )	Win (상수 시간 소요)
많은 메모리 사용	3) sparse 그래프에서	적은 메모리 사용
적은 메모리 사용	4) dense 그래프에서	많은 메모리 사용
O(n)	5) 삽입하거나 삭제	O(1)
O(n^2)	6) 탐색	O(m + n)
	7) most algorithm problems	효율성과 간편성을 고려하여 리스트가 더 좋음
데이터의 구조가 밀집적이고 행렬 연산이 빈번하게 발생하므로 행렬이 더 좋음	8) most data analysis problems