拓扑排序（有向图）：
从AOV网中选择一个入度为0的顶点输出，然后删去该顶点，并删除以此顶点为弧尾的弧，重复这个步骤，知道输出图中全部的顶点，或者找不到入度为0的顶点
如果这个图的全部顶点被输出，说明不存在回路的AOV网，否则，存在回路
拓扑排序可以不唯一
比如：
上面的图的拓扑排序：3,0,1,2或者0,1,3,2或者0,3,1,2
问题：
输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个整数，如果为1，则表示第i个顶点有指向第j个顶点的有向边，0表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。
如果读入的有向图含有回路，请输出“ERROR”，不包括引号。
如果读入的有向图不含有回路，请按照题目描述中的算法依次输出图的拓扑有序序列，每个整数后输出一个空格。
请注意行尾输出换行。
例如：
4
0 1 0 0
0 0 1 0
0 0 0 0
0 0 1 0
输出：
3 0 1 2
分析：
1，这是一个二维数组，用来存储a->b是否有边，需要定义一个二维数组
2，把每个点的入度的个数用一个数组存起来，比如下标0，标识0的入度点 的个数，下标1，标识1的入度点的个数，就是上面的二维数组的每列1的个数，就是对应的点的入度的个数
3，把入度为0的点存到栈中，然后依次出栈，并同时进入队列，队列存储的是拓扑序列，并定义一个count,计数器，用来存储出栈的个数
4，count==n的时候，说明所有点都遍历了，没有环路，返回队列，否则返回error
5，栈中元素出栈了，一直到栈中元素为空，每出一个元素，就看一下这个元素出度，所指的点，并把这个点的入度次数-1，就是刚刚把每个元素的入度个数存起来的数组，数组里面对应的个数-1，如果-1之后，变为了0，说明这个点的入度次数也就变为了0，没有了入度，可以进栈，一直循环
定义一个全局变量队列，用来存储拓扑序列
queue<int> q;
存储每个点的入度的个数,就是二维数组列为1的个数
int k[n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]!=0){
k[j]++;
}
}
}
定义一个栈，存储入度为0的点
stack<int> s;
for(int i=0;i<n;i++){
if(k[i]==0){
s.push(i);
}
}
栈中元素出栈，出去的存到队中，同时判断这个元素的出度对应的点的入度的个数-1，判断是否为了0了，为0，入栈
while(!s.empty()) {
int temp=s.top();
s.pop();
q.push(temp);
count++;
for(int i=0;i<n;i++）{
if(a[temp][i]!=0){
k[i]--;
if(k[i]==0){
q.push(i);
}
}
}
}
完整代码：
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
queue<int> q;//用来存储拓扑序列
bool tuopu(int **p,int n){
stack<int> s;//用来存储入度为0的点
int *k=new int[n];//用来存储节点的入度的个数
for(int i=0;i<n;i++){ //初始化为0
k[i]=0;
}
int count=0;//用来记录栈中出去的个数，如果最后==n了，就说明没有环图
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]!=0){
k[j]++; //记录从0到n的节点入度的个数
}
}
}
for(int i=0;i<n;i++){
if(k[i]==0){
s.push(i);//入度节点为0的进栈
}
}
while(!s.empty()){
int temp=s.top();
s.pop();
count++;
q.push(temp);
for(int i=0;i<n;i++){
if(p[temp][i]!=0){
k[i]--;
if(k[i]==0){//说明这个节点入度为0了，进栈了
s.push(i);
}
}
}
}
if(count==n){
return true;
}else{
return false;
}
}
int main()
{
int n;
while(cin>>n){
int **p=new int*[n];
for(int i=0;i<n;i++){
p[i]=new int[n];
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>p[i][j];
}
}
bool b=tuopu(p,n);
if(b){
//输出队列
while(!q.empty()){
cout<<q.front()<<" ";
q.pop();
}
}else{
cout<<"ERROR"<<endl;
}
}
return 0;
}
结果截图;
拓扑排序（无向图）：判断有无环
采用拓扑排序来做，因为无向图，如果有环，那么环中的元素的度肯定是>=2的，所以我使用删除节点方法来做，
1，度小于等于1的存到栈中
2，循环栈，每次循环都出一个元素，并将这个元素相对应的点的度-1，之后，判断相对应的这个点的度是否==1，如果等于1，进栈
3，一直循环直到栈为空
4，最后判断一下k中是否有>=2的，有就返回true，说明有环，否则返回false，没有环，k就是存储各个点的度
while(!s.empty())
{
int i=s.top();
cout<<i<<" ";
s.pop();
for(int j=0; j<n; j++)
{
if(p[i][j]!=0)
{
k[j]--;
if(k[j]==1)
{
s.push(j);
}
}
}
}
代码：
#include <iostream>
#include<stack>
using namespace std;
int n;
bool tuopu(int **p) //有环，返回true
{
int k[n];
for(int i=0; i<n; i++)
{
k[i]=0;
}
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(p[i][j]==1)
{
k[i]++;
}
}
}
stack<int> s;
//将k中<=1的存到栈中
for(int i=0; i<n; i++){
if(k[i]<=1){
s.push(i);
}
}
while(!s.empty())
{
int i=s.top();
//cout<<i<<" ";
s.pop();
for(int j=0; j<n; j++)
{
if(p[i][j]!=0)
{
k[j]--;
if(k[j]==1)
{
s.push(j);
}
}
}
}
for(int i=0; i<n; i++)
{
if(k[i]>=2)
{
//cout<<k[i]<<" ";
return true;
}
}
return false;
}
int main()
{
cin>>n;
int **p=new int*[n];
for(int i=0; i<n; i++)
{
p[i]=new int[n];
}
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
cin>>p[i][j];
}
}
bool b=tuopu(p);
cout<<b<<endl;
return 0;
}
结果：
