前言

图论真是枯燥我还跳过了树，好在已经过来了。

前面的内容比较简单，所以会短邑点

图的存储

图的存储有三种方式：

1. 邻接矩阵
2. 邻接链表
3. 链式前向星

其中，我们最常用的是邻接链表。

记住这个图：

下面会用这个图来举例。

邻接矩阵

定义一个二维数组 g，其中 g[u][v] 表示节点 $u$ 和节点 $v$ 是否相连。如下：

其中，如果边有权值，可以设为权值而不是 $1$。

• 添加边：要在 $u-v$ 添加一条边，只需要把 g[u][v] 设为 $1$ 或权值。
• 删除边：要删除 $u-v$ 之间的边，只需要把 g[u][v] 设为 $0$。
• 判断边：判断 $u-v$ 是否有边，只需要查找 g[u][v] || g[v][u]。
• 遍历边：枚举所有点，判断是否与 $u$ 相连。

优点

删边、添边极快，容易理解。

缺点

内存占用大（$O(m^2)$）。

遍历时间 $O(n)$。

邻接链表最常用

本质上是定义 $n$ 条链表，第 $u$ 条链表上是与 $u$ 相连的点。

但是使用链表极其繁琐，而 vector 正好可以解决这个问题。如表：

定义 vector <int> g[N]（$N$ 是常量，表示点数 $n$ 的最大值）。内容就和上表是一样的。

• 添加边：要添加 $u-v$ 边，只需要 g[u].push_back(v)。
• 删除边：要删除 $u-v$ 边，需要枚举 $u$ 的所有边，如果有 $u-v$，就删除（g[u].erase(g[u].begin() + k)）。
• 查找边：遍历 $u$ 的所有边，判断是否有 $v$ 与它相连。
• 遍历边：循环遍历 g[u]。

优点

内存占用小，添加边容易。

缺点

删边复杂。

链式前向星

定义一个 head[N]、edge[N][3]（或 {u,v,next}edge[N]）。

head[u] 表示与 $u$ 相连的第一条边在 edge 的位置。edge[id].u 表示这一条边的一段，edge[id].v 则是另一段，edge[id].next 表示 edge[id].u 的下一条边在 edge 的边号。

如表：

图的遍历

图的遍历常用的方式就是DFS 和 BFS。

DFS 遍历图

void dfs(状态列表)
{
	if (结束条件)
	{
		操作;
		return ;
	}
	
	for (遍历所有拓展状态)
	{
		if (可行)
		{
			标记;
			dfs(新状态);
			回溯;
		}
	}
}

在图的遍历中：

• 状态列表：必须包含 $u$（当前节点，除非用全局变量），可以包含其他内容。
• 结束条件：如果当前节点没有子节点或子节点都被访问过。可省略，因为这样后面的循环不会执行。
• 遍历所有拓展状态：即所有子节点。
• 可行：没有被访问过。
• 标记：标记为访问过。
• 新状态：就是新节点，通常用 $v$ 表示。
• 回溯：撤销标记。

邻接链表 DFS 代码

void dfs(int u)
{
	vis[u] = 1;
	for (int v : g[u])
		if (!vis[v])
			dfs(v);
}

好像有点短了 按需增加操作。

BFS 遍历图

void bfs()
{
	q.push(起点状态);
	vis[起点状态] = 1;
	while (!q.empty())
	{
		取出状态;
		if (结束状态) 退出; 
		for (遍历所有拓展状态 && !vis[拓展状态])
		{
			if (可行)
			{
				q.push(拓展状态);
				vis[拓展状态] = 1;
			}
		}
	}
	无解; 
}

BFS 邻接矩阵代码

void bfs(int s)
{
	q.push(s);
	vis[s] = 1;
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		
		for (int v : g[u])
		{
			if (!vis[v])
			{
				q.push(v);
				vis[v] = 1;
			}
		}
	}
}