拓扑排序（c++）不太懂，有没有大神，求教

Question

最近要写拓扑排序的程序，然后作为一名渣渣，并不是特别懂。课本上说的只说了大致的，我只知道它的思想，却写不出程序来。有没有大神愿意教我(*´ο`*)

Answer 1

有向图可以拓扑排序的条件是：图中没有环。
具体方法：
⑴ 从图中选择一个入度为0的点加入拓扑序列。
⑵ 从图中删除该结点以及它的所有出边（即与之相邻点入度减1）。
反复执行这两个步骤，直到所有结点都已经进入拓扑序列。

 #include <iostream>
#include <fstream>
#include <stack>
using namespace std;

ifstream fin("in.txt");
#define MAX_VERTEX_NUM 26

stack<int> s;

typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextarc;
    ArcNode(){nextarc=0;}
//  InfoType *info;
}ArcNode;

typedef struct VNode{
    int data;
    ArcNode *firstarc;
    VNode(){firstarc=0;}
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
    int kind;
}ALGraph;

bool TopologicalSort(ALGraph G,int *indegree)
{
    int i,k;
    for(i=1;i<G.vexnum+1;i++)
    {
        if(!indegree[i]){s.push(i);}
    }
    int count=0;
    ArcNode *p;
    while(!s.empty())
    {
        i = s.top();
        s.pop();
        cout<<G.vertices[i].data<<"-->";
        count++;
        for(p=G.vertices[i].firstarc;p;p=p->nextarc)
        {
            k = p->adjvex;
            indegree[k]--;
            if(!indegree[k])s.push(k);
        }
    }
    if(count<G.vexnum) return false;
    return true;
}


int main()
{
    int i;
    ALGraph g;
    cout<<"输入节点数和边数： ";
    fin>>g.vexnum>>g.arcnum;
    for(i=1;i<g.vexnum+1;i++)
        g.vertices[i].data = i;

    int b,e;
    ArcNode *p;
    int *indegree = new int[g.vexnum+1];    
    //注意 int *a=new int(n);  申请一个整型变量空间，赋初值为n，并定义一个整型指针a指向该地址空间 
    //int *indegree=(int *)malloc(sizeof(int)*(g.vexnum+1));
    memset(indegree,0,sizeof(int)*(g.vexnum+1));
    cout<<"逐一输入边的顶点对，形如 3 5 "<<endl;
    for(i=1;i<g.arcnum+1;i++)
    {
        cout<<"第"<<i<<"条边：";
        fin>>b>>e;
        p = new ArcNode();
        p->adjvex = e;
        p->nextarc = g.vertices[b].firstarc;
        g.vertices[b].firstarc = p;
        indegree[e]++;
        cout<<endl;
    }
    if(TopologicalSort(g,indegree))cout<<"正常完成！"<<endl;
    else cout<<"该有向图有回路！"<<endl;
    return 0;
}