DAG图：有向无环图
拓扑排序：只有DAG图才能成功实现拓扑排序
此算法将判断此图是否为DAG图，如果是DAG图，则输出其中一种拓扑序列
代码如下：
#include"stdafx.h"#include<cstdio>#include<vector>#include<iostream>#include<algorithm>#include<queue>#include<stack>using namespace std;const int maxn = 500;const int INF = 1e9;int Vertexnum, Edgenum;//顶点数、边数vector<int> adj[maxn];//存储图int innode[maxn];//记录每个结点的入度int vis[maxn] = { false };//标记顶点v是否已经加入到拓扑序列中void init() {//初始化每个结点入度都为0for (int i = 0; i < Vertexnum; i++) {innode[i] = 0;}}queue<int> q1, q2;bool toposort() {for (int i = 0; i < Vertexnum; i++) {//找出所有入度为0的顶点，加入队列中if (innode[i] == 0) {q1.push(i);//将入度为0的顶点加入队列vis[i] = true;//标记i被加入队列中}}while (!q1.empty()) {//如果队列非空int u = q1.front();//取队首元素q1.pop();for (int i = 0; i < adj[u].size(); i++) {//将从u出发能到达的点的入度进行减操作int v = adj[u][i];innode[v]--;}q2.push(u);//将此入度为0的顶点加入队列q2for (int i = 0; i < Vertexnum; i++) {//找入度为0的点加入队列if (innode[i] == 0 && vis[i] == false) {//如果入度为0且还未被加入队列q1.push(i);vis[i] = true;}}}if (q2.size() == Vertexnum) return true;//此图是DAG图，拓扑排序成功else return false;//否则此图不是有向无环图，拓扑排序失败}int main() {cin >> Vertexnum >> Edgenum;init();//初始化int start, end;//起点、终点for (int i = 0; i < Edgenum; i++) {cin >> start >> end;adj[start].push_back(end);innode[end]++;//入度加1}if (toposort() == true) {//如果排序成功，则输出其中一个拓扑序列int n = q2.size();for (int i = 0; i < n; i++) {cout << q2.front() << " ";q2.pop();}}else {cout << "此图不是DAG图，拓扑排序失败\n";}return 0;}
发现以上代码还是有些冗余，现改为如下：
#include"stdafx.h"#include<cstdio>#include<vector>#include<iostream>#include<algorithm>#include<queue>#include<stack>using namespace std;const int maxn = 500;const int INF = 1e9;int Vertexnum, Edgenum;//顶点数、边数vector<int> adj[maxn];//存储图int innode[maxn];//记录每个结点的入度//int vis[maxn] = { false };//标记顶点v是否已经加入到拓扑序列中void init() {//初始化每个结点入度都为0for (int i = 0; i < Vertexnum; i++) {innode[i] = 0;}}queue<int> q1, q2;bool toposort() {for (int i = 0; i < Vertexnum; i++) {//找出所有入度为0的顶点，加入队列中if (innode[i] == 0) {q1.push(i);//将入度为0的顶点加入队列}}while (!q1.empty()) {//如果队列非空int u = q1.front();//取队首元素q1.pop();for (int i = 0; i < adj[u].size(); i++) {//将从u出发能到达的点的入度进行减操作int v = adj[u][i];innode[v]--;if (innode[v] == 0) {q1.push(v);}}q2.push(u);//将此入度为0的顶点加入队列q2}if (q2.size() == Vertexnum) return true;//此图是DAG图，拓扑排序成功else return false;//否则此图不是有向无环图，拓扑排序失败}int main() {cin >> Vertexnum >> Edgenum;init();//初始化int start, end;//起点、终点for (int i = 0; i < Edgenum; i++) {cin >> start >> end;adj[start].push_back(end);innode[end]++;//入度加1}if (toposort() == true) {//如果排序成功，则输出其中一个拓扑序列int n = q2.size();for (int i = 0; i < n; i++) {cout << q2.front() << " ";q2.pop();}}else {cout << "此图不是DAG图，拓扑排序失败\n";}return 0;}
