如果G[u][v] = 1，说明有一条从 u 到 v 的边，否则没有从 u 到 v 的边。
邻接矩阵的使用 #include <iostream> using namespace std; const int maxn = 105; int G[maxn][maxn]; int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; G[u][v] = G[v][u] = 1; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cout << G[i][j] << " "; } cout << endl; } return 0; } 邻接表邻接表的思想是，对于图中的每一个顶点，用一个数组来记录这个点和哪些点相连。由于相邻的点会动态的添加，所以对于每个点，我们需要用vector来记录。
也就是对于每个点，我们都用一个vector来记录这个点和哪些点相连。比如对于一张有 10 个点的图，vector<int> G[11]就可以用来记录这张图了。对于一条从 a 到 b 的有向边，我们通过G[a].push_back(b)就可以把这条边添加进去；如果是无向边，则需要在G[a].push_back(b)的同时G[b].push_back(a)。
上图演示了一个图对应的邻接表。每一行的第一列表示的是最外层vector数组的下标。 邻接表的优缺点 优点
节省空间：当图的顶点数很多、但是边的数量很少时，如果用邻接矩阵，我们就需要开一个很大的二维数组，最后我们需要存储 n*n 个数。但是用邻接表，最后我们存储的数据量只是边数的两倍。
可以记录重复边：如果两个点之间有多条边，用邻接矩阵只能记录一条，但是用邻接表就能记录多条。虽然重复的边看起来是多余的，但在很多时候对解题来说是必要的。
缺点当然，有优点就有缺点，用邻接表存图的最大缺点就是随机访问效率低。比如，我们需要询问点 a 是否和点 b 连，我们就要遍历G[a]，检查这个vector里是否有 b 。而在邻接矩阵中，只需要根据G[a][b]就能判断。
因此，我们需要对不同的应用情景选择不同的存图方法。如果是稀疏图（顶点很多、边很少），一般用邻接表；如果是稠密图（顶点很少、边很多），一般用邻接矩阵。
当点数较多（多于 5000）时，使用邻接矩阵会超出空间限制，需要使用邻接表。
邻接表的实现 #include <iostream> #include <vector> using namespace std; const int maxn = 105; vector<int> G[maxn]; int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } for (int i = 1; i <= n; i++) { cout << i << " : "; for (int j = 0; j < G[i].size(); j++) { cout << G[i][j] << " "; } cout << endl; } return 0; } 图的存储（带权值） 邻接矩阵在前面，图中的边都只是用来表示两个点之间是否存在关系，而没有体现出两个点之间关系的强弱。比如在社交网络中，不能单纯地用0、1来表示两个人否为朋友。当两个人是朋友时，有可能是很好的朋友，也有可能是一般的朋友，还有可能是不熟悉的朋友。
我们用一个数值来表示两个人之间的朋友关系强弱，两个人的朋友关系越强，对应的值就越大。而这个值就是两个人在图中对应的边的权值，简称边权。对应的图我们称之为带权图。
如下就是一个带权图，我们把每条边对应的边权标记在边上：
带权图也分成带权有向图和带权无向图。前面学到的关于图的性质在带权图上同样成立。实际上，我们前面学习的图是一种特殊带权图，只不过图中所有边的权值只有1一种；而在带权图中，边的权值可以是任意的。
用邻接矩阵存储带权图和之前的方法一样，用G[a][b]来表示 a 和 b 之间的边权（我们需要用一个数值来表示边不存在，如0）。同样，对于无向图，这个矩阵依然是对称的。
如上所示，左边的图对应的右边的邻接矩阵 带权图的邻接矩阵 #include <iostream> #include <cstring> using namespace std; const int maxn = 105; int G[maxn][maxn]; int sum[maxn]; int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; G[u][v] = w; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cout << G[i][j] << " "; } cout << endl; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { sum[i] += G[i][j]; } } for (int i = 1; i <= n; i++) { cout << sum[i] << " "; } return 0; } 邻接表