C++ 从大数据SPARK框架的DAG引擎，再论有向无环图（DAG）的拓扑排序

#include <bits/stdc++.h>
using namespace std;
//图
int graph[100][100];
//是否访问过
int vis[100];
//节点的父节点
int parent[100];
int INF=999;
//节点数、边数
int n,m;
//初始化图，自己和自己的距离为0，和其它节点距离为 INF
void init() {
 for(int i=1; i<=n; i++) {
  for(int j=1; j<=n; j++) {
   if(i==j)graph[i][j]=0;
   else graph[i][j]=INF;
  }
  vis[i]=0;
  parent[i]=0;
 }
}
//交互式得到节点之间关系
void read() {
 int f,t,w;
 for(int i=1; i<=m; i++) {
  cin>>f>>t>>w;
  graph[f][t]=w;
 }
}
/*
*有向无环图中找环
* s：节点编号
* f：父节点编号
*/
int  findCircle(int s,int f) {
 //标记为已经访问
 vis[s]=true;
 parent[s]=f;
 //查找其子节点
 for(int i=1; i<=n; i++) {
  if( graph[s][i]!=INF && graph[s][i]!=0  ) {
   if( vis[i]==1 &&  i!=f ) { //找到回边
       parent[i]=s;
    return i;
   }
   return findCircle( i,s );
  }
 }
 return -1;
}
/*
*
*找出环上的所有点
*/
void findCircle(int s) {
 int p=parent[s];
 while(p!=s) {
  cout<<p<<"\t";
  p=parent[p];
 }
}

int main(int argc, char** argv) {
 cin>>n>>m;
 init();
 read();
 int res= findCircle(1,0);
 findCircle(res);
 cout<<res;
 return 0;
}

//测试数据
6 6
1 2 1
6 1 1
2 4 1
4 6 1
3 5 1
5 6 1

/*
*有向无环图中找环
* s：节点编号
*/
int findCircle(int s,int f) {
 if(vis[s]) {
  parent[s]=f;
  //如果进入栈时标记为 1，说明已经被访问过，有环存在
  return s;
 }
 //入栈时标记为已经访问
 vis[s]=true;
 parent[s]=f;
 //查找其子节点
 for(int i=1; i<=n; i++) {
  if( graph[s][i]!=INF && graph[s][i]!=0  ) {
   return findCircle( i,s );
  }
 }
 //出栈时恢复状态
 vis[s]=false;
 return -1;
}

/*
*
*找出环上的所有点
*/
void findCircle(int s) {
 int p=parent[s];
 while(p!=s) {
  cout<<p<<"\t";
  p=parent[p];
 }
}

int main(int argc, char** argv) {
 cin>>n>>m;
 init();
 read();
 int res= findCircle(1,0);
 findCircle(res);
 cout<<res;
 return 0;
}

#include <bits/stdc++.h>
using namespace std;
//图
int graph[100][100];
//是否访问过
int vis[100];
//节点的父节点
int parent[100];
int INF=999;
//节点数、边数
int n,m;
//栈，存储拓扑排序结果
queue<int> myq;
//计数器
int count=0;

//初始化图，自己和自己的距离为0，和其它节点距离为 INF
void init() {
 for(int i=1; i<=n; i++) {
  for(int j=1; j<=n; j++) {
   graph[i][j]=0;
  }
  vis[i]=0;
  parent[i]=0;
 }
}
//交互式得到节点之间关系
void read() {
 int f,t,w;
 for(int i=1; i<=m; i++) {
  cin>>f>>t>>w;
  graph[f][t]=w;
 }
}

//查找入度为 0 的节点且删除与之相邻的出边
int findNode(int i) {
 bool is=true;
 for(int j=1; j<=n; j++) {
  if( graph[j][i]!=0) {
   is=false;
   break;
  }
 }
 if(is) {
  for(int j=1; j<=n; j++) {
   graph[i][j]=0;
  }
 }
 return is;
}

//找到入度为0 的节点压入队列
void pushQueue() {
 for(int i=1; i<=n; i++) {
  if( findNode(i) && !vis[i] ) {
   //找到，入队列
   vis[i]=true;
   myq.push(i);
  }
 }
}

/*
*拓扑排序
*/
void tp() {
 //初始化入度为 0 的节点入队列
 pushQueue();
 while( !myq.empty() ) {
  int t=  myq.front();
  count++;
  cout<<t<<"\t";
  myq.pop();
  pushQueue();
 }
    //如果出队列的节点数量和原节点数量不相同，说明有环
 if( count!=n )cout<<"有环";
}

int main(int argc, char** argv) {
 cin>>n>>m;
 init();
 read();
 tp();
 return 0;
}

#include <bits/stdc++.h>
using namespace std;
//图
int graph[100][100];
//是否访问过
int vis[100];
//节点的父节点
int parent[100];
int INF=999;
//节点数、边数
int n,m;
//是否有环
int isCircle=0;
//栈，存储拓扑排序结果
stack<int> stk;
//自己和自己的距离为0
void init() {
 for(int i=1; i<=n; i++) {
  for(int j=1; j<=n; j++) {
   if(i==j)graph[i][j]=0;
   else graph[i][j]=INF;
  }
  vis[i]=0;
  parent[i]=0;
 }
}
//交互式得到节点之间关系
void read() {
 int f,t,w;
 for(int i=1; i<=m; i++) {
  cin>>f>>t>>w;
  graph[f][t]=w;
 }
}
/*
*有向无环图中找环
* s：节点编号
*/
void findCircle(int s,int f) {
 if(vis[s]) {
  parent[s]=f;
  isCircle=1;
  //如果进入栈时标记为 1，说明已经被访问过
  return;
 }
 //入栈时标记为已经访问
 vis[s]=true;
 parent[s]=f;
 //查找其子节点
 for(int i=1; i<=n; i++) {
  if( graph[s][i]!=INF && graph[s][i]!=0  ) {
   findCircle( i,s );
  }
 }
 //出栈时恢复状态
 vis[s]=false;
 //存储后序遍历结果
 stk.push(s);
}

/*
*拓扑排序
*/
void tp(int s,int f) {
 findCircle(s,f);
 if(isCircle) {
  return;
 }
 cout<<"tp sort:"<<endl;
 while(!stk.empty()) {
  cout<<stk.top()<<"\t";
  stk.pop();
 }
}
int main(int argc, char** argv) {
 cin>>n>>m;
 init();
 read();
 tp(1,0);
 return 0;
}
//测试数据
6 6
1 2 1
1 3 1
2 4 1
3 5 1
4 6 1
5 6 1