알고리즘 6 그래프_1

그래프란? 

정점의 모음과 간선의 모음이 결합 

G= G(V,E) 

 

인접/이웃관계 Adjacent ; 간선으로 연결되 두 정점 

경로 ; 

길이 ; 정점과 정점 사이의 간선의 숫자 

사이클 ; 정점을 두 번 이상 거치도록 되어 있을 경우 

방향성 ; 간선에 방향성이 있는 경우와 없는 경우 

연결성 ; 두 정점 사이에 간선이 있는 경우 

 

정점의 집합 -> 배열 또는 리스트로 나타냄 

간선의 집합 -> 행렬 또는 리스트로 나타냄 = 인접행렬 또는 인접리스트 

 

인접행렬 vs 인접리스트 

- 정점 간의 인접 인식 속도 ; 행렬 > 리스트

- 필요한 메모리 양 ; 행렬 > 리스트 

- 정점과 간선 삽입 속도 ; 행렬 < 리스트 

 

그래프 순회 기법 

- 깊이 우선 탐색 

- 너비 우선 탐색 

 

GitHub - Sukmin-LanternK/Algorithm