c++ 图论数据结构不用<map>实现吗？

Question

看书上说可以用<map>实现图的数据结构，而我百度了，几乎没找到这样的记录，是不好实现吗？

Answer 1

图论的常用算法需要的数据结构无外乎邻接矩阵和邻接表，邻接矩阵肯定是数组或者Vector了，邻接表的话用链表，每个元素又是数组，也可以用Vector,map的优势只是可以给顶点取一个不是数字的序号，而直接叫A,B,C,并没有明显优势。

Answer 2

map的话，可以用一对顶点的标识（例如id或者内存地址）组成的pair作为键，权重数字作为值。

这类似于用二维数组建立邻接矩阵。若邻接矩阵比较稀疏，用map比用二维数组空间上节省一些，时间上多耗费一些。