我的OI心得(八)之图论(七).docVIP

拓扑排序 很有用的东西（然而不是万能的）！ 我们做动态规划的时候，总有这么一个原则：对于某个状态，他的最值由他的某几个较小规模的状态决定。因此如果那几个较小规模的状态都到过当前状态了（就是“更新过”），我们才能用当前状态去更新别的状态。 这个动态规划的状态和决策构成一张图，就是说，对于某个点v1，只有指向v1的所有点都被访问过之后，v1才能被访问。比如v2指向v1，那么只要v2还没被访问，v1就不允许被访问。那好，我很懒，只希望你告诉我一个点集的排列，让我挨个去访问就好了，而且符合上面的规则。拓扑排序就可以把这个排列做出来，当然，不唯一。做出来的东西我们可以叫 点的拓扑序 。 怎么做呢？通常是这样： 维护一个数组din[i]，意义是点i的入度。我做个队列，先扫一遍所有的点，把din[i]=0的点都加到队列里面去。然后依次访问队列中的点i，访问完之后把i指向的点的入度-1，这个叫“拆边”。当某点的所有入边都被拆光的时候，说明这个指向这个点的点都被访问过了，这个点就能被访问了——加入队列。把所有点做完后，我们已经进行了一遍拓扑遍历——可以把工作在遍历的时候都做掉。 代码如下： var u{当前点},i{循环变量},n{点的总数},t1{队首指针},t2{队尾指针}:integer; q:array[1..maxn]of integer;{队列} din:array[1..maxn]of integer;{入度} g:array[1..maxn,1..maxn]of boolean;{邻接矩阵存图} flg:array[1..maxn]of boolean;{是否在队列里} t1:=1; t2:=0; for i:=1 to n do flg[i]:=false; for i:=1 to n do if din[i]=0 then begin inc(t2);q[t2]=i;end; while t1=t2 do begin u:=q[t1]; inc(t1); {该干吗干吗} for i:=1 to n do if g[u,i] then begin dec(din[i]); if din[i]=0 then if not flg[i] then begin inc(t2); q[t2]:=i; end; end; end; 注意——显然，如果图中存在环，那在环中的点就无法放到拓扑序列中。