图的表示方法

本篇将介绍图的四种表示方法

---

直接存边

使用结构体或者数组直接存边：

struct edge {
	int u, v; //边的首尾
	int w; //边的一些参数
}

int u[N], v[N], w[N] //使用数组直接存储

复杂度

• 查询一条边： $O(m)$
• 遍历一个点的所有出边：$O(m)$
• 遍历整张图：$O(nm)$
• 空间复杂度：$O(m)$

可以看出，这个存图方式导致如果你想要找到其中一条边的参数，需要遍历整张图才可以获得
太过缓慢了，除非是像 Kruskal 中这种需要按边权来排序的才比较方便

邻接矩阵

顾名思义，使用一个二维矩阵 $adj[u][v]$ 来表示从 $u$ 到 $v$ 的一条边的参数

struct edge {
	int w; //边的一些参数
} adj[N][N]; //创建二维矩阵

复杂度

• 查询一条边：$O(1)$
• 遍历一个点的所有出边：$O(n)$
• 遍历整张图：$O(n^2)$
• 空间复杂度：$O(n^2)$

邻接矩阵仅适用于图中没有重边的情况
其最显著的优点是查询边只需要 $O(1)$ 即可完成，最大的困难是需要占用 $O(n^2)$ 的空间，在稀疏图上效率较低

邻接表

使用 $vector<node>$ 动态数组来存储边的信息

struct node {
	int v; //出边信息
	int w; //参数信息
};

vector<node> adj[u]; //创建以u为起点的所有边的信息

复杂度

• 查询一条边：$O(d^+(u))$
• 遍历一个点的所有出边：$O(d^+(u))$
• 遍历整张图：$O(n+m)$
• 空间复杂度：$O(m)$

由于其中规中矩的性质以及高效率的空间使用，大多数情况存图我们都选择邻接表

链式前向星

通过手写链表，来组成一张图

int h[N], e[N], f[N], ne[N], idx;

void add(int u, int v, int w) {
	e[idx] = v; //边的终点
	f[idx] = w; //边的参数
	ne[idx] = h[u]; //将下一条边的指针指向原本的头
	h[u] = idx++; //将当前边作为下一个头
}

for(int i = h[u];~i;i = ne[i]) { //使用起点遍历边
	int ver = e[i]; //提取终点
}

复杂度

• 查询一条边：$O(d^+(u))$
• 遍历点u的所有出边：$O(d^+(u))$
• 遍历整张图：$O(n+m)$
• 空间复杂度：$O(m)$

链式前向星拥有非常优秀的性质，任何图都可以用这个存
他不能快速查询一条边是否存在，也不方便排序，所以通常我们仍然使用邻接表
但是当我们需要存反向边时，可以通过 i^1 快速访问，这点在 网络流 中被灵活运用