首页 > 代码库 > 白书 - 拓扑排序 及 关于递归、coding的一些思考

白书 - 拓扑排序 及 关于递归、coding的一些思考

题目:有n个变量,m个二元组(u,v),表示变量u小于变量v。将所有变量从小到大排列,给出满足条件的一个。

思路:把“小于”关系看成有向边,得到一个有向图。任务就是把一个图的所有结点排序,使得每一条有向边(u,v)对应的 u 都排在 v 的前面。在图论中,这个问题称为拓扑排序topological sort。  不难发现:如果图中存在有向环,则不存在拓扑排序的解,反之则存在。我们把不包含有向环的有向图称为有向无环图(Directed Acyclic Graph,DAG)。

以下是补充了输入部分后的书上的代码,这里输入的是整数,但它们之间的关系由随后的m个二元组给定,不是其自身的大小,然后n个变量(整数)的范围是从0到n-1.

这里用到 c 数组,c[u]=0表示从没有访问过(没有调用过dfs(u));c[u]=1表示已经访问过,且已递归访问过它的所有子孙(即dfs(u)曾被调用过,并已返回);c[u]=-1表示正在访问(即递归调用dfs(u)正在栈帧中,尚未返回)。

自己的思考:要很好地理解和自己会写递归程序,首先要知道一个递归函数它的作用是什么。比如之前二叉树重建那题里build(n,s1,s2,ans)的作用就是根据一个长度为n的先序序列s1和中序序列s2,构造一个长度为n的后序序列;这里的dfs(u)的含义是把u放在topo中满足条件的位置。你不能跟着它的递归一层层深入下去,你应该首先要搞清楚这个递归函数的作用,才能很好地理解它是怎么完成功能的。

另外,除了函数有他本身的意义,变量也有其自身的意义,比如这里的 t 就是指最新确定一个元素后它应该在topo中放置的位置。觉得程序的每个变量和函数都有它的意义,然后你在code时,就是要实现函数的功能,维护变量的意义。

然后就是scanf("(%d,%d)",&a,&b)时,由于 scanf 的格式化说明符中第一个是括号,是个字符,所以是不会跳过空白符的~会导致输入失败。

另外就是声明变量时还是立马赋初值比较好,即使马上对其进行scanf。因为scanf可能输入失败。比如这里a、b开始没赋初值,用scanf("(%d,%d)",&a,&b)输入,前面没有getchar,结果程序崩了,原因是换行符导致scanf输入失败,而 a , b 的初值可能超过数组G的下标了,所以产生段异常。而如果在for循环前加上getchar,结果程序没崩但输出是错误的,原因是第一次弃了换行符导致scanf可以读入,则a,b有了初值,虽然后面因为没有getchar来弃置换行符导致输入失败,但a,b的值都不会超过数组下标,所以不会崩溃,但结果是错误的。如果给a,b赋初值0,则不管scanf输入成功与否,都不会导致崩溃,更不会产生同是输入失败、但一个崩溃一个不崩溃这样奇怪的错误~

另外,关于拓扑排序的其他一些讨论,见:这里。

Code:

</pre><pre name="code" class="cpp">
</pre><pre name="code" class="cpp">#include<stdio.h>
#include<string.h>
#define MAXN 100

bool toposort();
bool dfs(int u);

int G[MAXN][MAXN];
int c[MAXN];
int topo[MAXN],t;
int n,m;

int main()
{
 int a=0,b=0;//变量还是赋初值比较好,不会引起如程序崩溃之类的奇怪错误,就算很快就对变量进行scanf。因为scanf可能失败。 
 while(scanf("%d%d",&n,&m)==2)//n个变量,m个二元组 
 {
  memset(topo,0,sizeof(topo));
  memset(G,0,sizeof(G));
  //getcahr(); 
  for(int i=0;i<m;++i)
  {
   //getchar();
   //scanf("(%d,%d)",&a,&b);//printf("%d",scanf("(%d,%d)",&a,&b));
   scanf("%d,%d",&a,&b);
   G[a][b]=1;                               
  }               
  if(toposort())
   for(int i=0;i<n;++i)
    printf("%d ",topo[i]); 
  else printf("failed.\n");               
 }
 return 0;
}

bool toposort()
{
 t=n;
 memset(c,0,sizeof(c));
 for(int u=0;u<n;++u)//遍历行 
  if(!c[u] && !dfs(u))//没有访问过u,且调用dfs(u)返回失败
   return false;
 return true;      
}

bool dfs(int u)
{
 c[u]=-1;
 for(int v=0;v<n;++v)//遍历列
  if(G[u][v])
  {
   if(c[v]<0) return false;//存在有向环
   else if(!c[v] && !dfs(v)) return false;//这里,放置u之前,先将未放置的、比u大的元素放置在合适位置。      
  }
 c[u]=1;
 topo[--t]=u;
 return true;    
}


白书 - 拓扑排序 及 关于递归、coding的一些思考