拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧<v，w>或存在从顶点v到w的路径则在该有向图的任一拓扑序列中，v一定在w之前。下面有向图的拓扑序列是

根据定义，拓扑序列中任一顶点的入度都为0，因此可以先找到入度为0的顶点。在下面的有向图中，入度为0的顶点有A和B。我们可以先将A和B加入拓扑序列中，并删除它们的出边。此时C和D的入度都为0，可以将它们加入拓扑序列中并删除它们的出边。最后，E的入度为0，将其加入拓扑序列中并删除其出边。因此，一个可能的拓扑序列是ABCD、ABDC、BACD、BADC、BCAD、BDAC。

A---->C---->E
 \        /
  \      /
   -->B--
       |
       v
       D

相关问题

对有向无环图，按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列。 输入有向图的相关信息，若图中无环，输出其拓扑有序序列，否则输出“此有向图不是有向无环图”。使用c++实现，给出完整代码

以下是使用C++实现的拓扑排序代码：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 1e5 + 5;

vector<int> adj[MAXN];
int in_deg[MAXN];

vector<int> topo_sort(int n) {
    vector<int> res;
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (in_deg[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        res.push_back(u);
        for (int v : adj[u]) {
            in_deg[v]--;
            if (in_deg[v] == 0) {
                q.push(v);
            }
        }
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        in_deg[v]++;
    }
    vector<int> res = topo_sort(n);
    if (res.size() != n) {
        cout << "此有向图不是有向无环图" << endl;
    } else {
        for (int i = 0; i < n; i++) {
            cout << res[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

输入格式为有向图的节点数n和边数m，接下来m行每行两个整数u和v，表示有一条从u指向v的有向边。程序会输出拓扑有序序列或者“此有向图不是有向无环图”。

具体实现是通过维护每个节点的入度，将入度为0的节点加入队列中，每次取出队列头部节点，将其邻接节点的入度减1，若减1后入度为0，则加入队列。最后得到的序列即为拓扑有序序列。若最后得到的序列长度不为n，则说明图中存在环，不是有向无环图。

用DEV C++写一个程序对有向无环图，按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列。 输入有向图的相关信息，若图中无环，输出其拓扑有序序列，否则输出“此有向图不是有向无环图”。 因拓扑有序序列不唯一，故要求如下： （1）使用邻接表存储图。邻接表的每个链表中，要求按顶点的序号从大到小排列； （2）使用栈辅助操作。初始时，入度为0的顶点入栈时，也按顶点的序号从大到小的顺序入栈。 输入说明： 输入有向图的顶点数、边数、各顶点的值，各边的信息。 输出说明： 若有向图中无环，输出其拓扑有序序列，否则输出“此有向图不是有向无环图”。 拓扑有序序列的每个顶点数据后有一个空格。

以下是用C++语言编写的程序，可实现对有向无环图进行拓扑排序：

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 10005;

struct Edge {
    int to, next;
};

Edge edges[MAXN];
int head[MAXN], inDegree[MAXN];
int N, M, cnt;

void addEdge(int from, int to) {
    edges[++cnt].to = to;
    edges[cnt].next = head[from];
    head[from] = cnt;
    inDegree[to]++;
}

bool topSort() {
    stack<int> st;
    for (int i = 1; i <= N; i++) {
        if (inDegree[i] == 0) st.push(i);
    }
    vector<int> ans;
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        ans.push_back(u);
        for (int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].to;
            inDegree[v]--;
            if (inDegree[v] == 0) st.push(v);
        }
    }
    if (ans.size() != N) return false;
    reverse(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    return true;
}

int main() {
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        int from, to;
        cin >> from >> to;
        addEdge(from, to);
    }
    if (!topSort()) cout << "此有向图不是有向无环图";
    return 0;
}

使用邻接表存储图，并使用一个 stack 存储入度为 0 的节点，在每次取出一个节点后更新其相邻节点的入度，并将入度为 0 的节点压入栈中。最终，如果所有节点都被排列，则说明拓扑排序成功，输出拓扑有序序列；否则，输出“此有向图不是有向无环图”。