그래프 자료구조를 C++ 로 표현하는 방법은 여러가지가 있는데, 보통 어떤 방법을 사용하나요?
편하게 구현하기 위해, 인접행렬을 씁니다.
m[a][b] = c; a 에서 b 로 가는 비용은 c 다.
메모리 비용이 많이 들고 연결된 부분을 찾기 위해선 탐색 시간이 소요됩니다.
좀 더 메모리 효율을 가져오기 위해선 인접 리스트 방식을 씁니다.
vector> graph;
메모리 효율이 좋고 속도가 빠르나, dfs, bfs 등등의 탐색을 적용하기엔 왠지 귀찮네요.
그리고 이 방법은 어떤가요? 인접 행렬과 인접리스트 방식의 중간형태인데,
map 을 이용해서 표현 하는 방법입니다.
typedef int vtype;
map > graph;
