拓扑排序

浏览数：33 / 时间：2015年06月08日

拓扑排序

拓扑排序主要有无前驱，无后继和dfs三种方法；

若只需判断是否为拓扑序列(DAG)，可用上述拓扑排序看是否排序成功，也可用floyd传递闭包；

无前驱的拓扑排序法：

/* 无前驱的拓扑排序法 */
bool toposort()
{
    queue<int> q;
    while(!ans.empty()) ans.pop();//记录结果
    memset(vis,0,sizeof(vis));  //vis数组
    int tmpdeg[maxn];
    memcpy(tmpdeg,indeg,sizeof(indeg));  //拷入入度附件，避免对原件操作造成后果

    for(int i=0;i<n;i++){  //入度为0的结点全部入队
        if(!tmpdeg[i]){
            q.push(i);
            ans.push(i+‘A‘);
            vis[i]=1;
        }
    }

    while(!q.empty()){   //队头结点的出边去掉并出队，并把去掉出边之后所有下一个入度为0的点入队
        int u=q.front();
        q.pop();
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];
            if(--tmpdeg[v]==0){
        q.push(v);
                ans.push(v+‘A‘);
                vis[v]=1;
            }
        }
    }

    for(int i=0;i<n;i++){   //检查是否有环，如果有未访问过的结点，说明有环
        if(!vis[i]) return false;
    }
    return tag;
}

无前驱的拓扑排序法

无后继的拓扑排序发和无前驱同理，只需将入度改为初度，反着写即可；

dfs拓扑排序法：

bool dfs(int u)
{
    vis[u]=-1;
    for(int v=1;v<=n;v++){
        if(G[u][v]){
            if(vis[v]==-1) return false;
            if(!vis[v]){
                if(!dfs(v)) return false;
            }
        }
    }
    ans.push(u);
    vis[u]=1;
    return true;
}

bool toposort()
{
    memset(vis,0,sizeof(vis));
    for(int u=1;u<=n;u++){
        if(!vis[u]){
            if(!dfs(u)) return false;
        }
    }
    return true;
}