[알고리즘 개념] 그래프

 

그래프

 

정점(노드)와 간선(엣지)로 이루어진 자료구조

간선의 방향 유무에 따라 단방향 그래프와 무방향 그래프로 나뉜다.

 

출처: https://m.blog.naver.com/occidere/220923695595

 

그래프의 표현

 

인접 행렬 그래프

: 모든 정점에 대해 연결 유무를 표시한다.

 

직관적이며 쉽게 구현이 가능하지만, 불필요한 정보의 저장이 많으며 메모리 차지가 크다

 

인접 리스트 그래프

: 간선이 존재하는 곳만 표시한다.

 

필요한 정보만 저장하기 때문에 메모리 차지는 적지만, 구현이 어렵다.

 

 

그래프 탐색

 

BFS/DFS https://validming99.tistory.com/74

[알고리즘 개념] 깊이 우선 탐색(DFS)와 너비우선 탐색(BFS)