学习日记 | 拓扑排序

在拓扑排序的序章里，你是我唯一确定的起点，也是永恒的终点。

引入

说到前置知识，其实也和拓扑排序有关：可以拿大学每学期排课的例子来描述这个过程，比如学习大学课程中有：「程序设计」，「算法语言」，「高等数学」，「离散数学」，「编译技术」，「普通物理」，「数据结构」，「数据库系统」等。按照例子中的排课，当我们想要学习「数据结构」的时候，就必须先学会「离散数学」，学习完这门课后就获得了学习「编译技术」的前置条件。当然，「编译技术」还有一个更加前的课程「算法语言」。这些课程就相当于几个顶点 u, 顶点之间的有向边 (u,v) 就相当于学习课程的顺序。教务处安排这些课程，使得在逻辑关系符合的情况下排出课表，就是拓扑排序的过程。

概念

由某个集合上的一个偏序得到该集合上的一个全序，这个操作叫做拓扑排序。人话就是给一个有向无环图的所有节点排序。

AOV网

AOV网的全称是Activity On Vertex Network，也就是顶点活动网络。与DAG(有向无环图)不同的是，AOV的活动都表示在顶点上。拓扑排序也可以解释为将 AOV 网中所有活动排成一个序列，使得每个活动的前驱活动都排在该活动的前面。

AOE网

与AOV对应的是AOE网，Activity On Vertex Network，带权，权可以表示一个活动持续的时间。

最优算法

把入度为0的顶点放在栈或队列中。当队列不为空时，删除一个顶点v，并更新与顶点v邻接的顶点入度。只要有一个顶点的入度降为0，就将它入队。拓扑排序就是顶点出队的顺序。

Kahn算法（入度BFS法）

vector<vector<int>>edges;
//邻接表和入度统计
vector<vector<int>>next;
vector<int>inDegree(n,0);
for(auto e:edges)
{
    next[e[0]].push_back(e[1]);
    inDegree[e[1]]++;
}
queue<int>q;
for(int i=0;i<n;i++)
{
    if(inDegree[i]==0)
    q.push(i);
}
//BFS处理
vector<int>res;
while(!q.empty())
{
    int cur=q.top();
    q.pop();
    res.push_back(cur);
    for(int v:next[cur])
    {
       if(--inDegree[v]==0)
       q.push(v);
    }
}

引申而来的洛谷题“选课”

免责声明

这道题看似和拓扑排序有关，先学什么再学什么，实则考的还是树形dp，和之前写过的题很像。所以下面的内容实际上和拓扑排序无关

代码

void dfs(int u)
{
	dp[u][1] = s[u];//以u为根节点，选1个课程的最大学分
	for (int v : tr[u])
	{
		dfs(v);
		for (int j = m + 1; j >= 1; j--)//需要从大往小来计算
		{
			for (int i = 0; i <= m + 1 - j; i++)//从m+1个课程中选出i个课程
			{
				if (dp[v][i])
				{
					dp[u][j + i] = max(dp[u][j + i], dp[u][j] + dp[v][i]);
				}
			}
		}
	}
}

理解

这里有好几个有意思的点：

1. 为什么这里都要用m+1，包括最后答案输出的也是dp[0][m+1]，由这个0也可以看出来，实际上是引入了一个虚拟头节点
2. 这里虚拟头节点的引入是为了让没有任何先修课程的课有父节点
3. 计算顺序问题，这里是一个很常见的套路。直接来去看看01背包和完全背包的区别。
   01背包和完全背包

总结

拓扑排序本身是一个比较简单的内容，用一个入度表+队列BFS就可以轻松解决。重点还是关注这个树形dp