合适的存图方式往往能事半功倍，这里介绍三种方式：邻接矩阵、邻接表、链式前向星。
邻接矩阵
1）存图思想
用一个矩阵来记录一个图，矩阵第 i 行第 j 列的值就表示顶点 i 到顶点 j 的权值
2 代码实现
1 #include<stdio.h>
2 #include<string>
3 const int V = 1000; //最大顶点数
4 int mat[V][V];
5
6 int main()
7 {
8 //初始化操作
9 //假设权值为0表示没有该边
10 memset(mat, 0, sizeof(mat));
11
12 //增加边
13 //增加顶点i到顶点j的权值为w的边
14 mat[i][j] = w;
15
16 //删除边
17 mat[i][j] = 0;
18
19 //查询边
20 mat[i][j]
21 } 3）优点
a.简单易学
b.对已确定的边进行操作效率高：对已确定的边（两顶点已知），进行增加、删除（或更改权值）、查询，都是O(1)的时间复杂度
4)缺点
a.过高的空间复杂度：这几乎是一个致命的缺点，对于顶点数V,邻接矩阵存图的空间复杂度高达O(V * V),顶点数高于10000就不用考虑了。对于稀疏矩阵，太浪费内存了
邻接表
对每个顶点，使用不定长的链表来存储从该点出发的所有边的情况，第 i 个链表的第 j 个值就是顶点 i 到顶点 j 的权值。
2）代码实现
1 #include<stdio.h>
2 #include<vector>
3 #include<string>
4 using namespace std;
5
6 const int V = 100000;
7 vector<int>e[V]; //定义了V个链表
8
9 int main()
10 {
11 int i,j,k;
12 //邻接链表的初始化
13 //将起点为"i "的链表清空
14 e[i].clear();
15
16 //增加边
17 //增加顶点"i"到顶点"j"的边
18 e[i].push_back(j);
19
20 //查询边值
21 //查询以"i"为起点的第"j"条边
22 e[i][j];
23
24 //寻找权值为k的边
25 for (int j = 0; j < (int)e[i].size(); j++)
26 {
27 if (e[i][j] == k)
28 {
29 //do something
30 }
31 }
32
33 } a.较为简单易学：数组转链表，定长转不定长
b.内存利用率较高：对于顶点数V、边数E,空间复杂度为O(V + E),能较好的处理稀疏图
c.对不确定的边操作比较方便：比如，要遍历从某点出发的某条边，不会像邻接矩阵一样可能遍历到不存在的边
4）缺点
a.重边不好处理：判重比较麻烦，还要遍历已有的边，不能直接判断；一般情况下使用邻接表存图是会存储重边的，不会做重边的判断
b.对确定边效率不高：比如对于给定
i->j
的边要进行查询或修改等操作只有通过遍历这种方式找到
链式前向星
主要的数据结构是边数组（存储边的数组），当然想要完美表示图，光有一个边集数组还不够，还要有一个数组每一个点的第一条边。同时，每一条边都需要存储接下来一条边的“指针”
1 #include<stdio.h>
2 #include<string>
3 const int V = 100000;
4 const int E = 100000;
5
6 //边结构体的定义
7 struct Edge
8 {
9 int to; //该边的另一个顶点
10 int w; //该边的权值
11 int next; //下一条边的数组下标
12 };
13
14 //head[i]表示顶点i的第一条边的数组下标，"-1"表示顶点i没有边
15 int head[V];
16 Edge edge[E];
17
18
19 //增加边
20 //新增加边"a -> b",该边的权值为w,数组下标为"id"
21 inline void AddEdge(int a, int b, int w, int id)
22 {
23 edge[id].to = b;
24 edge[id].w = w;
25 edge[id].next = head[a]; // 新增的边要成为顶点`a`的第一条边，而不是最后一条边
26 head[a] = id; //类似于链表的头插法，最后一条边指向"-1"
27 return;
28 }
29 int main()
30 {
31 int a,b,w;
32 //链式前向星的初始化
33 //只需要初始化顶点数组就可以了
34 memset(head, -1, sizeof(head));
35
36 //遍历从a出发的所有边
37 for (int i = head[a]; i != -1; i = edge[i].next)
38 {
39 //do something
40 if(edge[i].to == b) //找到边a -> b
41 if(edge[i].w == w) //找到权值为w的边
42 }
43 } a.内存利用率高：相比
vector
实现的邻接表而言，可以准确开辟最多边数的内存，不像
vector
实现的邻接表有爆内存的风险
b..对不确定的边操作比较方便：和邻接表一样不会遍历到不存在的边
a.操作复杂一点：要求比较熟练，不熟练写起来比较慢
b.重边不好处理：这点与邻接表一样，只有通过遍历判重
c.对确定边操作效率不高：也与邻接表一样，不能通过两点马上确定边，只能遍历查找
总结
对于邻接矩阵，由于内存消耗局限性的，几乎只能用于简单的图论题
邻接表存图是最为常见的一种方法，绝大部分采用C++STL中的
vector
实现，一般情况下大部分图论题目都能使用该存图方式。
而链式前向星是一种较好的用来代替邻接表的数据结构，在邻接表存图不能使用时可以使用，几乎可以用于全部图论题目。如果熟练掌握，可以作为主要的存图方法。
参考链接：izqt.github.io/2015/07/21/ACM图论之存图方式
个性签名：时间会解决一切