코딩테스트 준비를 하는데 그래프 쪽이 안한지가 오래되어 헷갈려서 다시 정리하는 글

개념

현상이나 사물을 정점과 간선으로 표현하는 것

무향 그래프 : 간선의 방향이 없는 양방향 그래프
유향 그래프 : 간선의 방향이 있는 그래프
가중치 : 그래프에 가중치를 추가해서 비용을 표기할 수 있다.

표현

그래프를 표현하는 방법에는 인접 행렬, 인접 리스트, 인접 배열, 인접 해시테이블 등이 있다.

인접 행렬과 인접 리스트

인접 행렬과 인접 리스트로만 표현 시 인접 행렬은 간선의 밀도가 아주 높을 때가 적합하며 인접 리스트는 정점에 비해 간선이 많지 않을 때 사용하는 것이 좋다.

인접 행렬

그래프의 해당 정점에서 이어지는 정점에 값을 준다.

예를 들어 위의 그래프에서는 1이 2,5와 이어지기 때문에 2,5에 해당하는 위치에 1을 넣어줬다.
또한 위 그래프는 무향 그래프이기 때문에 0과 1로만 표현되었다.

만약 가중치가 있다면 1 대신 가중치를 넣어준다.

인접 리스트

정점에 인접한 정점들을 연결 리스트로 매달아 표현하는 방법

인접 배열과 인접 해시 테이블

인접 배열

정점에 인접한 정점들을 연결리스트 대신 배열로 저장하는 방법
인접 배열 헤더에 인접한 정점이 몇개인지 표시해두면 탐색을 쉽게 할 수 있다.

※ 그림에서 2가 5에 인접한다고 오표기 되어있다.

인접 해시테이블