版本比较

旧版本 4

changes.mady.by.user zhongluqiang

保存于

比较

新版本 当前版本

changes.mady.by.user zhongluqiang

保存于

标识

  • 该行被添加。
  • 该行被删除。
  • 格式已经改变。

...

  1. 求出各顶点的入度，并将所有入度为0的顶点入栈。
  2. 在栈不为空的情况下，重复执行以下操作：
    1. 栈顶元素出栈，并保存到拓扑排序结果数组topo[]中；
    2. 顶点元素的所有邻接点入度减1，如果减1后入度为0，则入栈。
  3. 栈为空之后，如果拓扑排序输出的顶点数小于顶点总数，则说明有环，否则拓扑排序完成。

除了可以用栈来实现拓扑排序，还可以直接借助递归来实现，以下是拓扑排序的代码示例：

除了可以用栈来实现拓扑排序，还可以使用队列，或者直接借助递归来实现，以下是拓扑排序的代码示例：

代码块
#define MAXN 1005

vector<int> G[MAXN]; // 邻接表，G[i]表示i指向的结点
int n;               // 结点数

int topsort() {
    // 计算各个顶点的入度
    vector<int> indegree(n);
    for(int i = 0; i < n; i++) {
        for(auto &t : G[i]) {
            indegree[t]++;
        }
    }

    // 入度为0的先入队
    queue<int> Q;
    for(int i = 0; i < n; i++) {
        if(indegree[i] == 0) {
            Q.push(i);
        }
    }

    // 拓扑排序
    int count = 0;
    while(!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        count++;
        for(auto &t : G[cur]) { // 邻接点入度减1，如果为0，则入队
            indegree[t]--;
            if(indegree[t] == 0) {
                Q.push(t);
            }
        }
    }
    
    return count;
}

DFS+三色标记法形式：

code
代码块
#define MAXN 1005

vector<int> G[MAXN]; // 邻接表，G[i]表示i指向的结点
int n;               // 结点数

int visited[MAXN];   // 访问状态，0：未访问，1：访问中，2：已访问
int count;           // 结点计数
bool valid;          // 记录是否是合法的DAG，也就是是否存在环

void dfs(int u) {
    visited[u] = 1;
    for(auto &v : G[u]) {
        if(visited[v] == 0) {
            dfs(v);
        } else if(visited[v] == 1) {
            valid = false;
        }
    }
    visited[u] = 2;
    count++;
}

int topsort_DFS() {
    count = 0;
    valid = true;
    for(int i = 0; i < n; i++) {
        dfs(i);
    }
    return count;
}