本文共 1346 字，大约阅读时间需要 4 分钟。

【度娘说】：

对一个(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个得到该集合上的一个，这个操作称之为拓扑排序。

【实现】：

/*input:6 80 10 20 31 42 42 53 43 5output:V0 V3 V2 V5 V1 V4 */#include
   
    #include
    
     using namespace std;#define EleType int#define MAX_NUM 100typedef struct node {    EleType v;    struct node *next;}NodeType,*NodePointer;typedef struct {    int idegree;    NodePointer next;}GNode,*GPointer;GNode graph[MAX_NUM];int vn,en;  //顶点数和边数void CreatG() {    EleType et1,et2;    NodePointer tail;    cin>>vn>>en;        for(int i = 0; i
     
      >et1>>et2;		NodePointer np = new NodeType;        np->v = et2;        np->next = NULL;                if(graph[et1].next == NULL) {        	graph[et1].next = np;        }else {        	tail = graph[et1].next;       		while(tail->next != NULL ) {            	tail = tail->next;        	}        	tail->next = np;        }        graph[et2].idegree++;    }}void TopSort() {    int n,m;    int top;    NodePointer np;    top = -1;    for(int i = 0; i
      
       next) {                m = np->v;                graph[m].idegree--;                if(graph[m].idegree == 0) {                    graph[m].idegree = top;                    top = m;                }            }        }    }    cout<
      
     
    
   

转载地址：https://lipenglin.blog.csdn.net/article/details/50058245 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！