树与图的存储与遍历 | OI笔记

树与图的存储和遍历

图是一种数学结构，是由边和点构成的集合，图分为以下几种：

1. 有向图，边的行进是有方向的
2. 无向图，边的行进无方向，也可以转化为两个有向图
3. 树，树是一种无环连通图
4. 完全图：每一个点都与其他顶点相连接，完全图边数为 $n · (n - 1) / 2$
5. 平凡图：仅存在一个点的图
6. 零图：仅存在点而不存在边
7. 连通图：任意两个顶点之间都至少存在一条边，反之则为非连通图

图的度数的概念

无向图可直接计算连接的边的个数

有向图每一个节点都有两个度(入度和出度)，分别表示指向自己和自己指向的边的个数

特别地，对于每一个点，该点的入度和出度之和称为该点的度数

握手定理：所有顶点的度为边数的二倍，奇点(度数为奇数的点) 的数目一定是偶数

例如对于下面这张图

对于节点 3， 有两条边指向 3 ，因此节点 3 的入度为 2; 而节点 3 没有指向的边，因此节点 3 的出度为 0

显然对于一个无环图，必定存在一个入度为 0 的点; 对于一个有环图，必定没有任何一个点的入度为 0

有向图的存储方式：

1. 邻接矩阵：graph[a][b] 用于存储 $a$ 到 $b$ 的信息(权重或是否存在路线)，空间复杂度 $O(n^2)$ ，适合存储稠密图（边多点少）,可存储边权

值得注意的是，由于编译器空间的限制，邻接矩阵的常数最最大只能开到 2e3

2. 邻接表(链式前向星)：对于每一个点都开一个单链表，将每一个点所连通的节点存入这个点的单链表中。存储有权图可定义结构体数组

邻接表初始化：

const int N = 1e5 + 10, M = N * 2;

int h[N]; // h[i] 表示第 i 个点作为头节点，存储 i 指向的边
int idx = 0; // 存储当前枚举到的数组下标，即边的总数

// 注意：为方便使用 idx，规定边从 1 开始存储

struct node
{
	int val; // 指向点的值
	int w; // 表示第 i 条边的边权
	int nxt; // 表示与第 i 条边同起点的另一条边的存储位置
}enge[N];

memset(h, -1, sizeof h);

插边

void add(int u, int v, int w)
// 分别表示	插入节点 读取点的值 该边的边权
{
	edge[++ idx].w = w; // 在总链表中新建节点
	edge[idx].val = v; // 将该点值存储到新建节点
	edge[idx].nxt = h[u]; // 
	h[u] = idx;
}

存储权值，开 $w$ 数组存储即可

树和图的遍历

• 深度优先遍历(dfs)

前提准备：

bool st[N];
// 用于存储第 i 个点是否遍历过

·
dfs：

void dfs(int u)
// u 表示当前搜索到的点 
{
	st[u] = true; // 更新搜索状态
	for (int i = h[u]; i != -1; i = nxt[i])
	// 遍历以 u 点作头节点的单链表 
	{
		int j = e[i]; // 用于存储原图中连向的点 
		if (!st[j])  // 如果该点没有被遍历过 
			dfs(j); // 即遍历该点 
	}
}

值得一提的是，对于某些题目（如Acwing846-树的重心 可以在遍历过程中添加私货，如动态维护子节点个数

• 广度优先遍历(bfs)

前提准备：

bool d[N];
// 用于第 i 个点到起始节点的距离

bfs函数：

int bfs()
{
	int hh = 0, tt = 0;
	// 直接将起始位置放入队列中，所以 tt = 0
	q[0] = 1;
	// 初始化队列
	
	memset(d, -1, sizeof d);
	// -1 的点表示还没有遍历过
	// 在遍历的过程中向 d 数组存入距离起始点的距离
	
	d[1] = 0;
	// 起始位置定义
	
	while (hh <= tt)
	// 队列不空
	{
		int t = q[hh ++];
		// 取出队头同时将队头出队
		for (int i = h[t]; i != -1; i = nxt[i])
		// 查询队头 t 所指向的节点
		{
			int j = e[i];
			// 取出该节点的值
			if (d[j] == -1)
			// 如果未搜索过
			{
				d[j] = d[t] + 1;
				// 距离增加 1 
				q[++ tt] = j;
				// 将当前搜索到的点入队
			}
		}
	}
	// bfs模板
	
	return d[n];
	// 返回 n 节点到 起始位置 的最短距离
}

宽搜的重要应用 - 求图的拓扑序列

拓扑序列：若一个由图中所有满足点构成的序列 A 满足对于图中每条边(x, y)，x 在 A 中的出现都在 y 之前，则称 A 是该图的一个拓扑序列

对于以上的图，1, 2, 3 则是该图的最长拓扑序列

对于一个有向无环图，必定存在至少一个拓扑序列[^1]，而图中存在自环的图必定没有拓扑序列

结合前文所提到的入度和出度，我们可以将拓扑序列成立的条件归为以下几条：

• 入度为 0 (即没有边指向该节点)为序列首节点

依据以上条件，查找拓扑序的步骤如下：

1. 将所有入度为 0 的节点入队
2. 若队列非空，循环执行以下步骤：
3. 取出队头 t
4. 枚举 t 的所有出边
5. 删掉这条出边d[j] --;

如此操作之后，队列中的次序即为拓扑序，而出队时只是将指针向后移动一位，前面元素的次序仍然是不变的，因此只需要从 0 遍历输出拓扑序：

for (int i = 0; i < n; i ++)
	cout << q[i] << " ";

例题：Acwing848-有向图的拓扑序列

const int N = 1e5 * 5 + 10;

int n, m;
int h[N], e[N], nxt[N], idx;

int q[N], d[N];
// d 存储第 i 个点的入度 

bool topsort()
{
	int hh = 0, tt = -1;
	
	for (int i = 1; i <= n; i ++)
		if (!d[i]) q[++ tt] = i;
	
	while (hh <= tt)
	{
		int t = q[hh ++];
		
		for (int i = h[t]; i != -1; i = nxt[i])
		{
			int j = e[i];
			d[j] --;
			if (d[j] == 0)	q[++ tt] = j;
		}
	}
	
	return tt == n - 1;
	// 当 tt == n - 1 时一共有 n 个点进入 
}

void add(int a, int b)
{
	e[idx] = b;
	nxt[idx] = h[a];
	h[a] = idx ++;
}

int main()
{
	cin >> n >> m;
	
	memset(h, -1, sizeof h);
	
	for (int i = 0; i < m; i ++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
		d[b] ++;
	}
	
	if (topsort())
	{
		for (int i = 0; i < n; i ++)
			cout << q[i] << " ";
		cout << endl;
	}
	else puts("-1");
	
	return 0;
	
}

注：一张图的拓扑序可以有多种, 以上的程序会输出其中任意一种

[^1]:因此有向无环图也被称为 拓扑图