拓扑排序
一．定义
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序(Topological Sort),是将G中所有顶点排成一个线性序列,使得对图中任意一对顶点u和v,若＜u,v＞∈E(G),则u在线性序列中出现在v之前。通常将这样的线性序列称为满足拓扑次序(Topolgical Order)的序列,简称拓扑序列。
二．算法
1.无前趋的顶点优先:
(1)算法描述：
(a)从网中选择一个入度为零的顶点输出；
(b)删除该顶点及其于该点有关的所有边；
(c)是否还有入度为零的顶点？若有，执行(a)，否则结束。
算法实现
以邻接表为图的存储结构的算法：
a)扫描顶点表，将入度为零的顶点入栈；
b)当栈非空时：
输出栈顶元素v，出栈；
检查v的出边，将每条出边的终端顶点的入度减1，若该顶点入度为0，入栈；
c)当栈空时，若输出的顶点小于顶点数，则说明AOV网有回路，否则拓扑排序完成。
算法实现：
void Graph::Toplogicasort()//top是入度为0的顶点栈的栈顶指针
{
int top=-1;
for(int i=0;i<n;i++) //建立如度为0顶点的链栈
if (count[i]==0)
{
count[i]=top;
top=i;
}
for(int i=0;i<n;i++)
if(top==-1)
{
cout<<"Network has a cycle"<<endl;
return;
}
else
{
int j=top;top=count[top];//入度为0的顶点出栈
count<<j<<endl;
Edge<float> *l=NodeTable[j].adj;
while(l)
{
int k=l,dest;
if(--count[k]==0)
{
count[k]=top;//入度减至0的顶点进栈
top=k;
}
l=l->link;//取j的下一条出边
}
}
}
/*通常的拓扑算法要用两个数组，一个用来记录每个顶点的入度，当入度为0，则进栈
。另一个数组用作栈数组，记录入度为0的顶点。其实当入度为0的顶点进栈以后，count[ i ]
＝0就不再有用，所以可以用count[ i ]记录栈内下一个入度为0的顶点，top指向栈顶顶点号 */
拓扑排序在算法问题中的应用很普遍，下面举例说明：
一。神经网络(NOIP2003)
【问题背景】
人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热gate方向，兰兰同学在自学了一本神经网络的入gate书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。
【问题描述】
在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经
元之间至多有一条边相连，下图是一个神经元的例子：
[attachment=863322]
图中，X1—X3是信息输入渠道，Y1－Y2是信息输出渠道，C1表示神经元目前的状态，
Ui是阈值，可视为神经元的一个内在参数。
神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神
经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元
输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。
[attachment=863332]
兰兰规定，Ci服从公式：（其中n是网络中所有神经元的数目）
[attachment=863345]
公式中的Wji（可能为负值）表示连接j号神经元和 i号神经元的边的权值。当 Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒
它会向其他神经元传送信号，信号的强度为Ci。
如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。
现在，给定一个神经网络，及当前输入层神经元的状态（Ci），要求你的程序运算出最后网
络输出层的状态。
【输入格式】
输入文件第一行是两个整数n（1≤n≤20）和p。接下来n行，每行两个整数，第i＋1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wij，表示连接神经元i、j的边权值为Wij。
【输出格式】
输出文件包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状
态，两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态，并且按照编号由
小到大顺序输出！
若输出层的神经元最后状态均为 0，则输出 NULL。
【输入样例】
5 6
1 0
1 0
0 1
0 1
0 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1
【输出样例】
3 1
4 1
5 1
本题题目冗长，需要对题目进行转化。
题目中的神经元，可以看作是一个个孤立的结点。每一个传递关系就是一条有向边，起点为输入结点，边指向输出结点。所以神经网络就转化成为一个有向图。
由于题目规定，结点严格分层，即所有的点严格分成若干个阶段，就好比楼梯，每一个兴奋只能从上面一个阶梯走到下面一个阶梯（即只能从输入层转到输出层）。
因此，我们可以对结点进行拓扑排序。把每个结点放在相应的阶梯上，这样，递推关系就只能发生在相邻两个阶梯之间。对于递推关系，题目中虽然给出了一个递推公式，但是条件不甚明确，完整的公式应该为：
[attachment=863347]
这样，题目就转化成了一个简单的图论问题，步骤如下：
1． 拓扑排序，建立起相邻层的递推关系；
2． 递推求解。
例程如下：
#include<iostream>
#include<cstring>
using namespace std;
int w[30][30];
bool a[30][30];//邻接表
int c[30],u[30],f[30],cnt[30];//f,每个结点所在的层；cnt每个结点的入度
int top,n,e;
void toppx()
{
int i,j;
bool p=1;
top=0;
while(p)
{
p=0;
top++;
for(i=1;i<=n;i++)
if(cnt[i]==0)
{
p=1;
f[i]=top;
}
for(i=1;i<=n;i++)
if(f[i]==top)
{
for(j=1;j<=n;j++)
if(a[i][j])
cnt[j]--;
cnt[i]=-1;
}
}
top--;
}
int main()
{
int i,j,k,x,y,d;
while(cin>>n>>e)
{
memset(a,0,sizeof(a));
memset(cnt,0,sizeof(cnt));
memset(f,0,sizeof(f));
for(i=1;i<=n;i++)
cin>>c[i]>>u[i];
for(i=1;i<=e;i++)
{ cin>>x>>y>>d;
a[x][y]=1;
w[x][y]=d;
cnt[y]++;
}
toppx();
for(i=2;i<=top;i++)
for(k=1;k<=n;k++)
if(f[k]==i)
{
c[k]=-u[k];
for(j=1;j<=n;j++)
if(a[j][k]&&c[j]>0)
c[k]+=w[j][k]*c[j];
}
k=0;
for(i=1;i<=n;i++)
if(f[i]==top)
{
if(c[i]>0)
{
cout<<i<<" "<<c[i]<<endl;
k++;
}
}
if(k==0)
cout<<"NULL"<<endl;
}
return 0;
}
二。ZJU2003Substitution Cipher（判断拓扑排序是否唯一）
原题如下：
Antique Comedians of Malidinesia would like to play a new discovered comedy of Aristofanes. Putting it on a stage should be a big surprise for the audience so all the preparations must be kept absolutely secret. The ACM director suspects one of his competitors of reading his correspondece. To prevent other companies from revealing his secret, he decided to use a substitution cipher in all the letters mentioning the new play.
Substitution cipher is defined by a substitution table assigning each character of the substitution alphabet another character of the same alphabet. The assignment is a bijection (to each character exactly one character is assigned -- not neccessary different). The director is afraid of disclosing the substitution table and therefore he changes it frequently. After each change he chooses a few words from a dictionary by random, encrypts them and sends them together with an encrypted message. The plain (i.e. non-encrypted) words are sent by a secure channel, not by mail. The recipient of the message can then compare plain and encrypted words and create a new substitution table.
Unfortunately, one of the ACM cipher specialists have found that this system is sometimes insecure. Some messages can be decrypted by the rival company even without knowing the plain words. The reason is that when the director chooses the words from the dictionary and encrypts them, he never changes their order (the words in the dictionary are lexicographically sorted). String a1a2 ... ap is lexicografically smaller than b1b2 ... bq if there exists an integer i, i <= p, i <= q, such that aj=bj for each j, 1 <= j < i and ai < bi.
The director is interested in which of his messages could be read by the rival company. You are to write a program to determine that.
Input
The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. The first line of each case contains only two positive integers A, 1 <= A <= 26, and K, separated by space. A determines the size of the substitution alphabet (the substitution alphabet consists of the first A lowercase letters of the english alphabet (a--z) and K is the number of encrypted words. The plain words contain only the letters of the substitution alphabet. The plain message can contain any symbol, but only the letters of the substitution alphabet are encrypted. Then follow K lines, each containing exactly one encrypted word. At the next line is encrypted message.
Output
For each case, print exactly one line. If it is possible to decrypt the message uniquely, print the decrypted message. Otherwise, print the sentence 'Message cannot be decrypted.'.
Sample Input
2
5 6
cebdbac
cac
ecd
dca
aba
bac
cedab
4 4
cca
cad
aac
bca
bdac
Sample Output
abcde
Message cannot be decrypted.
这道题目意思晦涩，需要多读几遍才能明白大意：一个人要通过mail传递密文，加密方式是用与原文单词在一个字母表的其它单词来代替。输入 n,k，n表示要加密的字母范围是字母表的前n个字母，k表示有k个加密后的单词，这些单词的原文是按字典排序的，而且单词的字母均取自字母表的前n个字母。这些单词的原文又通过秘密途径传给收信人，这样收信人就可以通过原文，密文对照，产生密码本。
现在的问题是，有可能仅仅知道密文单词就能破译。注意题目中是按字典顺序选出k个单词，然后才加密的。加密的方式又是用同一个字母表的其它单词来代替，这样如果已知密文，要知道原文，就要知道密文中的每个字母在英文字母表前n个单词中的相对位置。这是一个一一对应的过程。
我们可以通过输入的密文单词之间字母的相对关系构建一个有向图来解决这个问题。密文单词1 a1a2....ap,密文单词b1b2...bq,如果ai!=bi,说明ai和bi表示的原文字母a0,b0的关系是：a0<b0，这样，ai和bi之间有一条有向边。
初步建立图以后，用warshall算法求图的传递闭包，这样有向图中任意可以到达的两个点i,j，均有link[ i ][j]=1;（i,j对应的原文字母i0,j0的关系为i0<j0)
然后统计每个顶点的出度，比如字母表中的字母a对应的密文是a0,此时a0的出度应该最多，为n－1，b对应的密文字母的出度应为n-2,以此类推。用pos统计每个顶点的出度，这样密文中的每个字母在英文字母表前n个单词中的相对位置就应该为：n-1-pos;
这样我们就能通过仅知密文[屏蔽]密码啦。但是这样做是有条件的。注意题目中的条件“each character exactly one character is assigned ”，即按照上述方法求出的每个顶点的出度应该是各不相同的。这样如果要仅知密文[屏蔽]密码，则按上述方法求出的每个顶点的出度应该各不相同，如果构成的图中有环或者孤立点存在，则至少存在两个相同的顶点的出度相同，就无法[屏蔽]密文。
综上，仅知密文[屏蔽]密码的条件可归结为，按照字典中先后关系构成的顶点图中，有唯一的拓扑排序
例程如下：
# include <iostream>
# include <string>
using namespace std;
//# define N 5000
//char st[N],sb[N],s[N];
string st,sb,s;
int link[30][30];
int main()
{
int block;
int i,j,k,m,n,pos;
int cipher[30];
cin>>block;
while(block--){
memset(link,0,sizeof(link));
cin>>n>>m;
cin.get();
cin>>st;
for(i=1;i<m;i++){
cin>>sb;
k=0;
while((st[k]==sb[k])&&(k<st.length())&&(k<sb.length())) k++;
if((k<st.length())&&(k<sb.length())){
link[st[k]-'a'][sb[k]-'a']=1;
//link[sb[k]-'a'][st[k]-'a']=-1;
}
st=sb;
}
for(k=0;k<n;k++)//求图的传递闭包
for(i=0;i<n;i++)
for(j=0;j<n;j++){
if(link[i][k]==1&&link[k][j]==1){
link[i][j]=1;
link[j][i]=-1;
}
}
for(i=0;i<n;i++)
{
pos=0;
for(j=0;j<n;j++)if(j!=i)
{
if(link[i][j]==1) pos++;
if(link[i][j]==0&&link[j][i]==0)
{
pos=-1;
break;
}
}
if(pos==-1) cipher[i]=-1;
else cipher[i]=n-1-pos;
}
char ch;
ch=cin.get();
getline(cin,s);
for(i=0;i<s.length();i++)if(s[i]<'a'+n&&s[i]>='a'){
if(cipher[s[i]-'a']!=-1) s[i]=cipher[s[i]-'a']+'a';
else break;
}
if(i==s.length()) cout<<s<<endl;//printf("%s\n",s);
else cout<<"Message cannot be decrypted."<<endl;
}
return 0;
}
三。ZJU 2193 Window Pains
大意：
Boudreaux 通常把九个程序一起运行。由于显示器资源的有限，他把窗口重叠，并且当他要用某个窗口的时候，他就把它调到最前端。如果他的显示器是一个 4 x 4 的方格，Boudreaux的每一个窗口就应该像下面那样用2 x 2的窗口表示:
[attachment=863352]
当Boudreaux 把一个窗口调到前端的时候，它的所有方格都到最前，覆盖它与其它窗口共用的方格。例如，如果窗口 1 然后 窗口 2 被调到当前, 结果应该表达为：
[attachment=863356]
. . . 等等等等 . . .
不幸的是, Boudreaux的电脑很不稳定。他通过观察窗口是否正确地被调到当前，一眼就能看出电脑是否死机。（其实学校机房的电脑经常这样）你的任务来了 . . .
Input
输入包含最多100组数据。每组数据将按下列描述给出，各组数据间无空行。
单组数据包含 3 部分：
1. START
2. 用四行表示当前Boudreaux的显示器状态。为使输入简单点，数字间仅用一个空格分开。
3. END
最后一组数据后，会有一行：
ENDOFINPUT
注意每个小块只能出现在它可能出现的地方。例如 1 只能出现在左上方的四个小格里。
Output
对每个数据只输出一行。如果能按一定顺序调出窗口达到数据描述的那样（即没死机），输出:
THESE Windows ARE CLEAN
否则：
THESE WINDOWS ARE BROKEN
Sample Input
START
1 2 3 3
4 5 6 6
7 8 9 9
7 8 9 9
END
START
1 1 3 3
4 1 3 3
7 7 9 9
7 7 9 9
END
ENDOFINPUT
Sample Output
THESE WINDOWS ARE CLEAN
THESE WINDOWS ARE BROKEN
解题思路：
看似是一道比较复杂的题啊，有些同学可能一拿到题就会去想各种各样的判断规则，其实那些都只能是隔靴搔痒，没有抓到题目的要害，我们要找出的是题目里最关键的信息，然后利用它来解决这道题目。
我们先可以想象，假如有一个正常的屏幕给我们，它们可能会是这种显示：
[attachment=863379]
我们将这个屏幕的样子解释一下： 1 、 2 、 7 、9四个窗口被盖在最下面，4 盖住1和7，5在最上面。
而一个格子通常最多只能被4个窗口盖住（这个应该不需要我解释把），只要当前点是被其中的一个窗口覆盖，则这个窗口则肯定盖住其他可以覆盖这个点的窗口。
比如：
[attachment=863372]
其中（2，2）这个格子可以被1、2、4、5 四个窗口覆盖，但在当前它是被5窗口覆盖的，则可以知道5窗口必定覆盖了1、2、4这三个窗口。
则我们就可以根据这个覆盖关系构一个有向图 5 -----> 1、2、4。 表示 5 覆盖这些窗口。
那么可以得到，如果我们已知一个正常的屏幕，那么通过这个屏幕构建出来的图肯定是一个有向无环图（ 因为不可能A窗口覆盖了B，而B窗口又反过来覆盖了A）。 而判断一个有向无环图就可以使用拓扑排序算法。 这样题目的解法就很明朗了。
1： 通过给出的屏幕构建有向网络。
2： 通过拓扑排序算法判断该网络是否有环，如果存在环，则该屏幕为死机后屏幕，否则则为正常屏幕。
友情提示： 我们可以在构建网络之前先算出一个数组Cover [ i,][ j ]，它是一个字符串，表示能覆盖（i，j）这个点的窗口的集合，有了这个数组，构图的时候就比较方便了。
例程如下：
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int n=4;
int screen[4][4];//屏幕最后显示的内容
string cover[4][4];//表示能覆盖（I，J）这个点的窗口的集合
bool exist[10]; //某个数据是否在屏幕上出现
int id[10]; //入度
bool g[10][10];//邻接表
int t;//记录屏幕上总共出现的不同的数据种类，以这些数据为顶点，构建有向图
string s;
void calc()
{
int k,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cover[i][j].clear();
for(k=1;k<=9;k++)//统计覆盖（I，J）这个点的窗口的集合
{
i=(k-1)/3;
j=(k-1)%3;
cover[i][j]+=char(k+'0');
cover[i][j+1]+=char(k+'0');
cover[i+1][j]+=char(k+'0');
cover[i+1][j+1]+=char(k+'0');
}
}
void init()
{
int i,j,k;
memset(id,0,sizeof(id));
memset(exist,0,sizeof(exist));
memset(g,0,sizeof(g));
t=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
cin>>k;
screen[i][j]=k;
if(!exist[k])
t++;
exist[k]=true;
}
}
void build()
{
int i,j,p;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(p=0;p<cover[i][j].length();p++)
{
if((!g[screen[i][j]][cover[i][j][p]-'0'])&&(screen[i][j]!=cover[i][j][p]-'0'))
{
g[screen[i][j]][cover[i][j][p]-'0']=true;
id[cover[i][j][p]-'0']++;//入度加1
}
}
}
bool check()
{
int i,k,j;
for(k=0;k<t;k++)
{
i=1;
while(!exist[i]||(i<=9&&id[i]>0))
i++;
if(i>9) //出现了环
return false;
exist[i]=false;
for(j=1;j<=9;j++)
if(exist[j]&&g[i][j])
id[j]--;
}
return true;
}
int main()
{
calc();
while(cin>>s)
{
if(s=="ENDOFINPUT")
break;
init();
build();
if(check())
cout<<"THESE WINDOWS ARE CLEAN\n";
else cout<<"THESE WINDOWS ARE BROKEN\n";
cin>>s;
}
return 0;
}
四。ZJU1083（输出拓扑排序的全部可能）
Consider the following 5 picture frames placed on an 9 x 8 array
[attachment=863373]
Now place them on top of one another starting with 1 at the bottom and ending up with 5 on top. If any part of a frame covers another it hides that part of the frame below.
Viewing the stack of 5 frames we see the following.
[attachment=863374]
In what order are the frames stacked from bottom to top? The answer is EDABC.
Your problem is to determine the order in which the frames are stacked from bottom to top given a picture of the stacked frames. Here are the rules:
1. The width of the frame is always exactly 1 character and the sides are never shorter than 3 characters.
2. It is possible to see at least one part of each of the four sides of a frame. A corner shows two sides.
3. The frames will be lettered with capital letters, and no two frames will be assigned the same letter.
INPUT DATA
Each input block contains the height, h (h<=30) on the first line and the width w (w<=30) on the second. A picture of the stacked frames is then given as h strings with w characters each.
Example input:
9
8
.CCC....
ECBCBB..
DCBCDB..
DCCC.B..
D.B.ABAA
D.BBBB.A
DDDDAD.A
E...AAAA
EEEEEE..
Your input may contain multiple blocks of the format described above, without any blank lines in between. All blocks in the input must be processed sequentially.
OUTPUT DATA
Write the solution to the standard output. Give the letters of the frames in the order they were stacked from bottom to top. If there are multiple possibilities for an ordering, list all such possibilities in alphabetical order, each one on a separate line. There will always be at least one legal ordering for each input block. List the output for all blocks in the input sequentially, without any blank lines (not even between blocks).
Example Output:
EDABC
题目分析：
题目的大意是 几个由字母组成的方框（边框是大写字母，中间由.组成），按照某种顺序重叠起来。现在已知重叠后的图案，编程输出方框从底到顶的排列顺序。
这是一道又可以归为拓扑排序的问题。方框2如果在方框1的上面，那么方框2的边框必然和方框1的边框有重叠。如字母B重叠了字母A，则字母A表示的顶点到字母B表示的顶点之间就有一条有向边。算法过程是：
1： 通过给出的屏幕构建有向网络。
2： 通过搜索输出所有符合要求的排列顺序（按字典顺序）；
现在关键问题是如何构建有向网络，即如何判断某个字母重叠了另外的字母。首先要确定方框的位置，注意题目中的“ It is possible to see at least one part of each of the four sides of a frame. A corner shows two sides.”，可以确定方框四个顶点的位置，然后在4条边框上搜索，如果存在和这个方框字母不同的其它字母，则构成一条有向边。
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
bool used[30],graph[30][30];
char frame[30][30];
int id[30];//入度
int n,h,w;
string s;
//确定方框四个顶点的位置
void location(char ch,int &xmax,int &xmin,int &ymax,int &ymin)
{
int i,j;
xmax=ymax=0;
xmin=ymin=32767;
for(i=0;i<h;i++)
for(j=0;j<w;j++)
if(frame[i][j]==ch)
{
if(i>xmax) xmax=i;
if(i<xmin) xmin=i;
if(j>ymax) ymax=j;
if(j<ymin) ymin=j;
}
}
void count(char ch,int xmin,int xmax,int ymin,int ymax)
{
int i,j;
for(i=xmin;i<=xmax;i++)
for(j=ymin;j<=ymax;j++)
if(frame[i][j]!=ch&&frame[i][j]!='.')
{
if(!graph[ch-'A'][frame[i][j]-'A'])
{
graph[ch-'A'][frame[i][j]-'A']=true;
id[frame[i][j]-'A']++;
}
}
}
void build()//构建有向网络
{
int i;
char ch;
int xmax,xmin,ymax,ymin;
for(i=0;i<=25;i++)
if(used[i])
{
ch=char(i+'A');
location(ch,xmax,xmin,ymax,ymin);
//在4条边框上搜索，如果存在和这个方框字母不同的其它字母，则构成一条有向边。
count(ch,xmin,xmin,ymin,ymax);
count(ch,xmax,xmax,ymin,ymax);
count(ch,xmin,xmax,ymin,ymin);
count(ch,xmin,xmax,ymax,ymax);
}
}
void t_sort(int k,string s)//搜索，输出拓扑排序的所有可能性
{
int backup[30],i,j;
int len;
string str;
char ch;
if(k==n+1)
{
cout<<s<<endl;
return ;
}
for(i=0;i<30;i++)
backup[i]=id[i];
for(i=0;i<=25;i++)
if(used[i]&&id[i]==0)
{
id[i]=1;
for(j=0;j<=25;j++)
if(graph[i][j])
id[j]--;
ch=char(i+'A');
// s+=ch;
t_sort(k+1,s+ch);
for(j=0;j<30;j++)
id[j]=backup[j];
/* len=s.length();
str=s.substr(0,len-1);
s=str;*/
}
}
int main()
{
int i,j;
while(cin>>h>>w)
{
memset(graph,0,sizeof(graph));
memset(used,0,sizeof(used));
memset(id,0,sizeof(id));
n=0;
s.clear();
for(i=0;i<h;i++)
{
for(j=0;j<w;j++)
{
cin>>frame[i][j];
if(frame[i][j]!='.'&&!used[frame[i][j]-'A'])
{
used[frame[i][j]-'A']=true;
n++;
}
}
}
build();
t_sort(1,s);
}
return 0;
}
[ 此贴被tongmeng在2007-01-09 17:17重新编辑 ]
