그래프 자료구조를 C++ 로 표현하는 여러가지 방법에 대해

그래프 자료구조를 C++ 로 표현하는 방법은 여러가지가 있는데, 보통 어떤 방법을 사용하나요?

편하게 구현하기 위해, 인접행렬을 씁니다.
m[a][b] = c; a 에서 b 로 가는 비용은 c 다.
메모리 비용이 많이 들고 연결된 부분을 찾기 위해선 탐색 시간이 소요됩니다.

좀 더 메모리 효율을 가져오기 위해선 인접 리스트 방식을 씁니다.
vector> graph;
메모리 효율이 좋고 속도가 빠르나, dfs, bfs 등등의 탐색을 적용하기엔 왠지 귀찮네요.

그리고 이 방법은 어떤가요? 인접 행렬과 인접리스트 방식의 중간형태인데,
map 을 이용해서 표현 하는 방법입니다.

typedef int vtype;
map > graph;

graph[a][b] = c 형태로, 기본적으로 해시를 쓰기 때문에 메모리 효율은 그렇게 좋진 못하지만,
프로그래밍 하기에 간편하고 연결된 부분을 찾기 위해서 걸리는 시간도 그리 크지 않습니다. 어떤가요?
노드 삭제도 간단합니다.
graph[ a ].erase(b);
graph[ b ].erase(a);

그리고 STL 을 이용해서 일반적으로 어떠한 방법으로 그래프를 표현하는지 궁금합니다.
또, 제시된 방법에 대해서 어떻게 생각하시는지 알려주세요~~