拓扑排序 | immix's blog

介绍

拓扑排序可以将一个有向无环图（DAG）的节点进行排序，排序后即可依次进行处理，使得排在前面的节点不能依赖于排在后面的节点，这样就可以满足 DP 的无后效性，进行 DP 求解某些问题。

Kahn 算法

Kahn 算法的步骤如下：

从图中入度为 0 的节点的集合中任取一个，并加入拓扑序；
删除该顶点和所有与其相连边；
重复 1-2 步，直到图中没有入度为 0 的节点。若此时图中还有边，说明图中有环。

如以下伪代码：

\begin{algorithm}
\caption{Kahn's Algorithm}
\begin{algorithmic}
\STATE $ L \leftarrow $ Empty list that will contain the sorted elements
\STATE $ S \leftarrow $ Set of all nodes with no incoming edge
\WHILE{$S$ \textrm{is not empty}}
    \STATE  remove a node $n$ from $S$
    \STATE  add $n$ to $L$
    \FOR {each node $m$ with an edge $e$ from $n$ to $m$}
        \STATE remove edge $e$ from the \textit{graph}
        \IF{if $m$ has no other incoming edges}
            \STATE insert $m$ into $S$
        \ENDIF
    \ENDFOR

\ENDWHILE

\IF {\textit{graph} has edges}
    \STATE return error   (\textit{graph} has at least one cycle)
\ELSE 
    \STATE return $L$   (a topologically sorted order)
\ENDIF
\end{algorithmic}
\end{algorithm}

以下是算法的一个示例：

Kahn 算法示例

在实现过程中，一般用一个队列维护入度为 0 的节点，并使用数组维护每个点的入度。在删边时，无需真正从图中删边，只需减小该点的入度即可。若入度减小为 0，则将其加入队列。在 DAG 上，这样一定能不重不漏的遍历每个节点（想一想，为什么）。最后只需判断是否从集合中取出了 $n$ 个节点即可判断是否存在拓扑排序。

实现如下:

const int N = 100;
queue<int> q; // 入度为0的点的集合
vector<int> G[N]; // 邻接表
int in[N]; // 每个点的入度
int n;
vector<int> res; // 拓扑排序结果

bool topo(){
    for(int i=1;i<=n;i++){
        for(int v:G[i]){
            in[v]++; // 统计入度
        }   
    }

    for(int i=1;i<=n;i++){
        if(in[i]==0)q.push(i);
    }
    int cnt=0;
    while(q.size()){
        cnt++;
        int u=q.front();q.pop();
        res.push_back(u);
        for(int v:G[u]){
            in[v]--; // 修改入度
            if(in[v]==0)q.push(v);
        }
    }
    return cnt==n; // 是否存在拓扑排序
}

时间复杂度 $O(V+E)$ 。

DFS 算法

DFS 算法中，对于节点 $u$ ，只有在 $u$ 的所有后继加入拓扑排序后， $u$ 才能加入拓扑排序，来实现了拓扑排序。具体来说，就是在 DFS 过程的回溯中加入拓扑排序。

伪代码如下：

\begin{algorithm}
\caption{DFS Algorithm}
\begin{algorithmic}
\STATE $L \leftarrow$ Empty list that will contain the sorted nodes
\WHILE{exists nodes without a permanent mark}
    \STATE select an unmarked node n
    \STATE \CALL{dfs}{n}
\ENDWHILE

\FUNCTION{dfs}{node $n$}
    \IF{$n$ has a permanent mark}
        \STATE return
    \ENDIF
    \IF{$n$ has a temporary mark}
        \STATE stop   (graph has at least one cycle)
    \ENDIF

    \STATE mark $n$ with a temporary mark

    \FOR{each node $m$ with an edge from $n$ to $m$}
        \STATE \CALL{dfs}{m}
    \ENDFOR

    \STATE mark $n$ with a permanent mark
    \STATE add $n$ to head of $L$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

vector<int> G[N]; // 邻接表
int vis[N];
int n;
vector<int> res; // 拓扑排序结果 （*反序）

bool dfs(int u){
    if(vis[u]==1)return true;
    if(vis[u]==-1)return false; // 有环

    vis[u]=-1;
    for(int v:G[u]){
        if(!dfs(v))return false;
    }
    vis[u]=1;

    res.push_back(u);
    return true;
}

bool topo(){
    for(int i=1;i<=n;i++){
        if(vis[i]!=1 && !dfs(i))return 0;
    }
    reverse(res.begin(),res.end());
    return 1;
}