树与图的存储与遍历 | 学习笔记

树与图的存储和遍历

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

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

根据图的点集 $n$ 与边集 $m$ 之间的关系，可以分为稀疏图和稠密图

• 当 $m$ 的数据范围与 $n^2$ 同一个级别时，属于稠密图
• 当 $m$ 的数据范围与 $n$ 同一个级别时，属于稀疏图

图的度数的概念

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

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

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

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

例如对于下面这张图

对于节点 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 head[N]; // head[i] 表示第 i 个点作为头节点，存储 i 指向的边
int idx = 0; // 存储当前枚举到的数组下标，从 1 开始使用，表示边的总数

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

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

memset(head, -1, sizeof head);

插边

inline void add(int u, int v, int w) {
// 分别表示	插入边的源点 指向点的值 该边的边权
	edge[++ idx].w = w; // 在总链表中新建节点
	edge[idx].to = v; // 将该点值存储到新建节点
	edge[idx].nxt = head[u]; // 将该点指向原 head 指向的节点
	head[u] = idx; // 将头节点指向该节点
}

树和图的遍历

深度优先遍历($dfs$)

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

模板

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

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

广度优先遍历 ($bfs$)

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

$bfs$ 模板：

queue<int> q;
int bfs() {
	memset(d, -1, sizeof d);
	// -1 的点表示还没有遍历过
	// 在遍历的过程中向 d 数组存入距离起始点的距离

	q.push(1), d[1] = 0;
	// 初始化根节点
	while (q.size()) {
	// 队列不空
		int t = q.front(); q.pop();
		// 取出队头同时将队头出队
		for (int i = head[t], j; i != -1; i = nxt[i]) {
		// 查询队头 t 所指向的节点
			j = to[i];
			// 取出该节点的值
			if (d[j] == -1) {
			// 如果未搜索过
				d[j] = d[t] + 1; // 距离增加 1 
				q.push(j); // 将当前搜索到的点入队
			}
		}
	}
	return d[n];
	// 返回 n 节点到 起始位置 的最短距离
}

宽搜的重要应用 - 拓扑排序 $topsort$

拓扑序列：若一个由图中所有满足点构成的序列 $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-有向图的拓扑序列

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 = head[t], j; i != -1; i = nxt[i]) {
			j = e[i];
			d[j] --;
			if (d[j] == 0)	q[++ tt] = j;
		}
	}
	return tt == n - 1;
	// 当 tt == n - 1 时一共有 n 个点进入 
}

int main() {
	cin >> n >> m;
	memset(head, -1, sizeof head);
	
	for (int i = 0, a, b; i < m; i ++) {
		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]:因此有向无环图也被称为 拓扑图