拓扑排序的应用

这是一篇关于拓扑排序的总结，以 LeetCode.1203 为例

例子的问题不再复述，总的来说，就是需要进行两次拓扑排序，第一次对组内的元素进行排序，第二次对组之间进行排序。

拓扑排序的大概过程：

取出所有入度为 0 的点放入队列 $q$ .
取出一个点 $t$ ，将其加入结果 $ans$ 数组中，并遍历其出边指向的点集 $S$ .
对于每个点 $s_i$ ，入度减 1，如果此时其入度为 0 ，将其放入 $q$ .
如果 $q$ 中无节点输出 $ans$ , 否则返回 2 步

正常的拓扑排序就比较简单，这里还要考虑条件冲突的情况（即例如 A 要求 B 在 A 前，B 要求 A 在 B 前），就是图中出现了环形依赖。

利用拓扑排序的特点，这个问题也容易解决，因为拓扑排序要求图是有向无环图，所以如果出现环，得到的排序将会不完整，所以根据得到的结果的节点数是否等于原来的节点数即可知道是否出现环，而如果出现环，即表示无解，直接返回空数组。

下面说明 LeetCode.1203 的解。

首先得到一个根据每个节点入度数和出边对应的节点进行拓扑排序的函数：

// A 为节点编号，inn为入度数组，out为每个点对应的后续节点
function sortInOut(A, inn, out) {
	const q = [], nA = [];
	for (const a of A) {
		if (inn[a] === 0) q.push(a); // 先将入度为 0 的点放入队列
	}
	while (q.length) { // 当队列不空就一直执行
		const t = q.shift(); 
		nA.push(t); // 取出头结点并加入结果中
		for (const v of out[t]) {
			inn[v]--;
			if (inn[v] === 0) q.push(v);
		}
	}
  // 下面判断是否无解
	if (nA.length !== A.length) return [];
	return nA;
}

使用这个函数，首先对每一个 group 子数组排序，再对 group 进行排序，因此剩下的就是分别构建子数组和 group 对应的 inn 和 out。主函数代码如下：

var sortItems = function (n, m, gp, bf) {
	let gn = m;
	for (let i = 0; i < n; i++) {
		if (gp[i] === -1) gp[i] = gn++; // 这里先将 -1 的组都编上号
	}

  // 要构建的四个数组
	const inn = nArray(n, () => 0), out = nArray(n),
		ginn = nArray(gn, () => 0), gout = nArray(gn);

	const inner = nArray(gn); //inner[i] 表示第 i 组的子数组
	for (let i = 0; i < n; i++) {
		inner[gp[i]].push(i);
		const b = bf[i]; // i节点的前序节点集
		for (const v of b) {
			// v before i
      // 下面将依赖关系分成两组，如果同组则认为这个依赖是**组内依赖**
      // 否则认为是组间依赖
      // 例如 v 在 i 前，如果两个点同组，即 gp[v] === gp[i]，则可以在组内满足这条依赖
      // 如果不同组，则我们只要让 gp[i] 在 gp[v] 之前就可以保证依赖满足
			if (gp[v] === gp[i]) { 
				inn[i]++;
				out[v].push(i);
			} else {
				ginn[gp[i]]++;
				gout[gp[v]].push(gp[i]);
			}
		}
	}

  // 这里进行组内排序
	for (let k = 0; k < gn; k++) {
		const ninner = sortInOut(inner[k], inn, out);
		if (ninner.length !== inner[k].length) return [];
		inner[k] = ninner;
	}
  // 这里进行组间排序
	const pos = sortInOut(inner.map((v, i) => i), ginn, gout);
  // 按照排序后的 index 拼接出结果
	const ans = [];
	for (const p of pos) {
		ans.push(...inner[p]);
	}
	return ans;
};

拓扑排序的应用

FEATURED TAGS

FRIENDS