拓扑排序

拓扑排序:对有向图的所有结点排序,使得每一条有向边(u,v)对应的u都排在v的前面。

如果图中存在有向环,则不存在拓扑排序,反之则存在。把不包含有向环的有向图称为有向无环图(Directed Acyclic Graph,DAG)。

//因为查找的是有向边(u,v),所以在放置u之前需要把比u偏序大的所有的v放置好。
//所以,所有元素的放置是从后往前放的。
//用到的vis数组,vis[u]=0表示从没有访问过u,即从没有调用过dfs(u); vis[u]=1表示已经访问过,并且还递归访问过它的所有子孙或偏序大于它的顶点,即dfs(u)曾被调用过且已返回;vis[u]=-1表示正在访问,即递归调用dfs(u)正在栈帧中,尚未返回。 
int vis[MAXN];
int topo[MAXN],t;

bool dfs(int u)
{
  vis[u]=-1;//正在访问,dfs(u)尚未返回
  for(int v=0;v<n;++v)
   if(G[u][v])
   {
     if(vis[v]<0) return false;//存在有向环,失败退出
     if(!vis[v] && !dfs(v)) return false;//这里调用dfs(v),意在放置u之前,先将未放置过的比u偏序大的元素放置好         
   }
  vis[u]=1;
  topo[--t]=u;
  return true;
}

bool toposort()
{
  t=n;//记录新元素要放的位置的后一位置,即当前结果的最首元素的位置
  memset(vis,0,sizeof(vis));
  for(int u=0;u<n;++u)
   if(!vis[u])
   {
     if(!dfs(u)) return false;         
   }   
  return true;
}
相关文章
相关标签/搜索