图的概念

这是图的基本样式，其中，$V_i$ 称为顶点，连接顶点的是边。在无向图中，一个节点连边的条数称为此节点的度数。在有向图中，一个结点向别的结点连边的条数称为这个结点的出度，别的结点连边到一个结点的条数称作这个结点的入度。

每条边的属性值，例如图中的 $a_i$，就称为边权。顶点也可以有属性值，称为点权。

两个顶点间，如果有不止一条边直接连接，称为重边。若一条边起点、终点都相同，称为自环。

若图中每一条边都可以双向通行，称这个图为无向图；若图中的边都只能从一个顶点到另一个顶点，或者一对顶点间有一来一回两条边，称这个图为有向图。需要注意的是，只有两条边起点、终点都一致才称为重边（比如上面提到“一来一回”的不称为重边）。

若一个图没有环，且是有向图，称其为**有向无环图（Directed Acyclic Graph, DAG）。**DAG 有许多可以拓展的内容。

图的建立

邻接矩阵

没有重边的情况下，使用一个二维数组 $v[i][j]$ 表示图，其中 $v[i][j]$ 的值表示从点 $i$ 到点 $j$ 的边权或路径长度。如果只关心是否有连通，则有连通可视为 $1$，不连通视为 $0$.

如果是有向图，则 $v[i][j]=v[j][i]$，因为双向连通，边权相等。假如换为无向图，就不一定对称了。

#include <bits/stdc++.h>
using namespace std;
#define N 1005
int n; // n 个点
int v[N][N];
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			cin >> v[i][j]; // 读入边权，没有则为 0
		}
	}
	return 0;
}

邻接表

邻接表的主要思想是，对于一条有向边 $\langle i, j\rangle$，只需要一个点能到达的顶点和相应边的边长即可。这可以定义 $\text{edge}$ 结构体存放这个边的终点 $\text{to}$ 和边权 $\text{cost}$。对于整个图的存储，我们开一个二维数组，第一维是起点，第二维存放以这个点为起点的边的集合。第二维使用动态数组 $\text{vector}$ 实现。

#include <bits/stdc++.h>
using namespace std;
#define N 1005
int n, m; // n 个点，m 条边
struct edge {
	int to, cost;
};
vector<edge> p[N];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, w; // u 为起点，v 为终点，w 为边权
		cin >> u >> v >> w;
		p[u].push_back((edge){v, w});
		// p[v].push_back((edge){u, l});
		// 若是无向图，要建一条反向边
	}
	return 0;
}